<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222" media="(prefers-color-scheme: light)">
<meta name="theme-color" content="#222" media="(prefers-color-scheme: dark)"><meta name="generator" content="Hexo 5.4.2">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">



<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.1.1/css/all.min.css" integrity="sha256-DfWjNxDkM94fVBWx1H5BMMp0Zq7luBlV8QRcSES7s+0=" crossorigin="anonymous">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/animate.css/3.1.1/animate.min.css" integrity="sha256-PR7ttpcvz8qrF57fur/yAx1qXMFJeJFiA6pSzWi0OIE=" crossorigin="anonymous">

<script class="next-config" data-name="main" type="application/json">{"hostname":"mathieulin.gitee.io","root":"/","images":"/images","scheme":"Gemini","darkmode":true,"version":"8.12.1","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":{"enable":false,"style":null},"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"stickytabs":false,"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/search.xml","localsearch":{"enable":true,"trigger":"manual","top_n_per_article":1,"unescape":false,"preload":false}}</script><script src="/js/config.js"></script>

    <meta name="description" content="这是一个记载了lzhow传奇的一生的博客">
<meta property="og:type" content="website">
<meta property="og:title" content="Mathieu&#39;s blog">
<meta property="og:url" content="https://mathieulin.gitee.io/index.html">
<meta property="og:site_name" content="Mathieu&#39;s blog">
<meta property="og:description" content="这是一个记载了lzhow传奇的一生的博客">
<meta property="og:locale" content="zh_CN">
<meta property="article:author" content="Mathieu Lin">
<meta property="article:tag" content="lzh">
<meta name="twitter:card" content="summary">


<link rel="canonical" href="https://mathieulin.gitee.io/">



<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":true,"isPost":false,"lang":"zh-CN","comments":"","permalink":"","path":"index.html","title":""}</script>

<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>Mathieu's blog</title>
  




<link rel="dns-prefetch" href="https://blog-commeny-mh5e4d5jo-mathieulin.vercel.app">
  <noscript>
    <link rel="stylesheet" href="/css/noscript.css">
  </noscript>
<link rel="alternate" href="/atom.xml" title="Mathieu's blog" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏" role="button">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <h1 class="site-title">Mathieu's blog</h1>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">lzhow的debug路程</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu"><li class="menu-item menu-item-home"><a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a></li><li class="menu-item menu-item-about"><a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a></li><li class="menu-item menu-item-tags"><a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a></li><li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a></li><li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a></li><li class="menu-item menu-item-schedule"><a href="/schedule/" rel="section"><i class="fa fa-calendar fa-fw"></i>日程表</a></li><li class="menu-item menu-item-sitemap"><a href="/sitemap.xml" rel="section"><i class="fa fa-sitemap fa-fw"></i>站点地图</a></li><li class="menu-item menu-item-commonweal"><a href="/404/" rel="section"><i class="fa fa-heartbeat fa-fw"></i>公益 404</a></li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup"><div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close" role="button">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</div>
        
  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-overview-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author site-overview-item animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">Mathieu Lin</p>
  <div class="site-description" itemprop="description">这是一个记载了lzhow传奇的一生的博客</div>
</div>
<div class="site-state-wrap site-overview-item animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
        <a href="/archives/">
          <span class="site-state-item-count">14</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
        <span class="site-state-item-count">8</span>
        <span class="site-state-item-name">分类</span>
      </div>
      <div class="site-state-item site-state-tags">
        <span class="site-state-item-count">9</span>
        <span class="site-state-item-name">标签</span>
      </div>
  </nav>
</div>
  <div class="links-of-author site-overview-item animated">
      <span class="links-of-author-item">
        <a href="https://github.com/mathieulin" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;mathieulin" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:19241032@buaa.edu.cn" title="E-Mail → mailto:19241032@buaa.edu.cn" rel="noopener" target="_blank"><i class="fab fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="http://121.199.35.110/" title="Todo → http:&#x2F;&#x2F;121.199.35.110&#x2F;" rel="noopener" target="_blank">Todo</a>
      </span>
      <span class="links-of-author-item">
        <a href="http://noietch.cn:88/" title="House → http:&#x2F;&#x2F;noietch.cn:88&#x2F;" rel="noopener" target="_blank">House</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://vkceyugu.cdn.bspapp.com/VKCEYUGU-05d97c93-6101-4c53-8659-f5cf79396b93/0cdfad7c-f758-49ca-becf-6483b8fe95d5.apk" title="Douzero → https:&#x2F;&#x2F;vkceyugu.cdn.bspapp.com&#x2F;VKCEYUGU-05d97c93-6101-4c53-8659-f5cf79396b93&#x2F;0cdfad7c-f758-49ca-becf-6483b8fe95d5.apk" rel="noopener" target="_blank">Douzero</a>
      </span>
      <span class="links-of-author-item">
        <a href="/atom.xml" title="rss → &#x2F;atom.xml"><i class="fa fa-rss fa-fw"></i>rss</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://mathieulin.github.io/myblog" title="Another-blog → https:&#x2F;&#x2F;mathieulin.github.io&#x2F;myblog" rel="noopener" target="_blank">Another-blog</a>
      </span>
  </div>



        </div>
      </div>
    </div>
    <iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width=330 height=86 src="//music.163.com/outchain/player?type=2&id=1951671851&auto=1&height=66"></iframe>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top" role="button" aria-label="返回顶部">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner index posts-expand">

    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="https://mathieulin.gitee.io/2023/09/22/super2121/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Mathieu Lin">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Mathieu's blog">
      <meta itemprop="description" content="这是一个记载了lzhow传奇的一生的博客">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | Mathieu's blog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2023/09/22/super2121/" class="post-title-link" itemprop="url">未命名</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>
      

      <time title="创建时间：2023-09-22 15:25:29 / 修改时间：15:49:50" itemprop="dateCreated datePublished" datetime="2023-09-22T15:25:29+08:00">2023-09-22</time>
    </span>

  
  
  <span class="post-meta-item">
    
    <span class="post-meta-item-icon">
      <i class="far fa-comment"></i>
    </span>
    <span class="post-meta-item-text">评论数：</span>
  
    <a title="waline" href="/2023/09/22/super2121/#waline" itemprop="discussionUrl">
      <span class="post-comments-count waline-comment-count" data-path="/2023/09/22/super2121/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <p>[TOC]</p>
<h1 id="C1"><a href="#C1" class="headerlink" title="C1"></a>C1</h1><h2 id="A-主定理"><a href="#A-主定理" class="headerlink" title="A 主定理"></a>A 主定理</h2><p><img src="/.io//Users\15128\AppData\Roaming\Typora\typora-user-images\image-20230922095545132.png" alt="image-20230922095545132"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> t, a, b, k;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t);</span><br><span class="line">	<span class="keyword">while</span>(t--)&#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d%d%d&quot;</span>, &amp;a, &amp;b, &amp;k);</span><br><span class="line">		<span class="type">long</span> <span class="type">long</span> x = <span class="number">1</span>;</span><br><span class="line">		<span class="keyword">if</span>(b &gt; <span class="number">1</span>)&#123;</span><br><span class="line">			<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= k &amp;&amp; x &lt;= a;i++) x *= b;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(a == x) <span class="built_in">puts</span>(<span class="string">&quot;n^k\\log n&quot;</span>);</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span>(a &gt; x) <span class="built_in">puts</span>(<span class="string">&quot;n^&#123;\\log_ba&#125;&quot;</span>);</span><br><span class="line">		<span class="keyword">else</span> <span class="built_in">puts</span>(<span class="string">&quot;n^k&quot;</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h2 id="B-一元多项式"><a href="#B-一元多项式" class="headerlink" title="B 一元多项式"></a>B 一元多项式</h2><p><img src="/.io//Users\15128\AppData\Roaming\Typora\typora-user-images\image-20230922100302735.png" alt="image-20230922100302735"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> M 10007</span></span><br><span class="line"><span class="type">long</span> <span class="type">long</span> a[<span class="number">1000001</span>],b[<span class="number">1000001</span>];</span><br><span class="line"><span class="type">long</span> <span class="type">long</span> n,m,x,y,i,t,c;</span><br><span class="line"><span class="function"><span class="type">long</span> <span class="type">long</span> <span class="title">Horner</span><span class="params">(<span class="type">long</span> <span class="type">long</span> *a,<span class="type">long</span> <span class="type">long</span> n,<span class="type">long</span> <span class="type">long</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(n&lt;<span class="number">1</span>)</span><br><span class="line">		<span class="keyword">return</span> a[<span class="number">0</span>] % M;</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">		<span class="built_in">return</span> (a[<span class="number">0</span>] % M + (<span class="built_in">Horner</span>(a+<span class="number">1</span>,n<span class="number">-1</span>,x) * x) % M) % M;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%lld&quot;</span>,&amp;n);</span><br><span class="line">	<span class="keyword">for</span>(i=<span class="number">0</span>; i&lt;=n; i++) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%lld&quot;</span>,&amp;a[i]);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%lld&quot;</span>,&amp;m);</span><br><span class="line">	<span class="keyword">for</span>(i=<span class="number">0</span>; i&lt;=m; i++) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%lld&quot;</span>,&amp;b[i]);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%lld&quot;</span>,&amp;c);</span><br><span class="line">	<span class="keyword">while</span>(c--)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%lld %lld&quot;</span>,&amp;x,&amp;y);</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%lld\n&quot;</span>,( (<span class="built_in">Horner</span>(a,n,x) % M) * (<span class="built_in">Horner</span>(b,m,y) % M) ) % M );</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="模运算"><a href="#模运算" class="headerlink" title="模运算"></a>模运算</h2><p><img src="/.io//image-20230922100525536.png" alt="image-20230922100525536"></p>
 <figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> maxn 100086</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> p = <span class="number">1e9</span> + <span class="number">6</span>;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> t, n;</span><br><span class="line"><span class="type">int</span> a[maxn], f[maxn], g[maxn];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t);</span><br><span class="line">	<span class="keyword">while</span>(t--)&#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;n);</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= n;i++) <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;a[i]);</span><br><span class="line">		f[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= n;i++) </span><br><span class="line">            f[i] = <span class="number">1ll</span> * f[i - <span class="number">1</span>] * a[i] % p;</span><br><span class="line">		g[n + <span class="number">1</span>] = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = n;i;i--) </span><br><span class="line">            g[i] = <span class="number">1ll</span> * g[i + <span class="number">1</span>] * a[i] % p;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= n;i++) </span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, <span class="number">1ll</span> * f[i - <span class="number">1</span>] * g[i + <span class="number">1</span>] % p);</span><br><span class="line">        <span class="built_in">puts</span>(<span class="string">&quot;&quot;</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="D-日期统计"><a href="#D-日期统计" class="headerlink" title="D 日期统计"></a>D 日期统计</h2><p><img src="/.io//image-20230922100849235.png" alt="image-20230922100849235"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> inf 0x3f3f3f3f</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> eps 1e-14</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> maxn 300005</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> ll;</span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">double</span> ld;</span><br><span class="line"><span class="keyword">typedef</span> <span class="type">unsigned</span> <span class="type">long</span> <span class="type">long</span> ull;</span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="type">int</span> <span class="title">read</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="type">int</span> x = <span class="number">0</span>, f = <span class="number">1</span>;</span><br><span class="line">	<span class="type">char</span> ch = <span class="built_in">getchar</span>();</span><br><span class="line">	<span class="keyword">while</span> (ch &gt; <span class="string">&#x27;9&#x27;</span> || ch &lt; <span class="string">&#x27;0&#x27;</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span> (ch == <span class="string">&#x27;-&#x27;</span>)</span><br><span class="line">			f = <span class="number">-1</span>;</span><br><span class="line">		ch = <span class="built_in">getchar</span>();</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">while</span> (ch &gt;= <span class="string">&#x27;0&#x27;</span> &amp;&amp; ch &lt;= <span class="string">&#x27;9&#x27;</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		x = x * <span class="number">10</span> + ch - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">		ch = <span class="built_in">getchar</span>();</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> x * f;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="type">char</span> s[<span class="number">10</span>], t[<span class="number">10</span>];</span><br><span class="line"><span class="type">int</span> y[<span class="number">2</span>], m[<span class="number">2</span>], d[<span class="number">2</span>];</span><br><span class="line"><span class="type">int</span> mx[<span class="number">13</span>] = &#123;<span class="number">0</span>, <span class="number">31</span>, <span class="number">28</span>, <span class="number">31</span>, <span class="number">30</span>, <span class="number">31</span>, <span class="number">30</span>, <span class="number">31</span>, <span class="number">31</span>, <span class="number">30</span>, <span class="number">31</span>, <span class="number">30</span>, <span class="number">31</span>&#125;;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">bool</span> <span class="title">check</span><span class="params">(<span class="type">int</span> a, <span class="type">int</span> b, <span class="type">int</span> c)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="type">int</span> s[<span class="number">10</span>], t = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= <span class="number">2</span>; i++)</span><br><span class="line">		s[++t] = c % <span class="number">10</span>, c /= <span class="number">10</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= <span class="number">2</span>; i++)</span><br><span class="line">		s[++t] = b % <span class="number">10</span>, b /= <span class="number">10</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= <span class="number">4</span>; i++)</span><br><span class="line">		s[++t] = a % <span class="number">10</span>, a /= <span class="number">10</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= <span class="number">8</span>; i++)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="type">bool</span> f = <span class="number">1</span>;</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> j = i + <span class="number">1</span>; j &lt;= <span class="number">8</span>; j++)</span><br><span class="line">			<span class="keyword">if</span> (s[j] &lt; s[j - <span class="number">1</span>])</span><br><span class="line">				f = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> j = i - <span class="number">1</span>; j &gt;= <span class="number">1</span>; j--)</span><br><span class="line">			<span class="keyword">if</span> (s[j] &lt; s[j + <span class="number">1</span>])</span><br><span class="line">				f = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">if</span> (f)</span><br><span class="line">			<span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">		f = <span class="number">1</span>;</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> j = i + <span class="number">1</span>; j &lt;= <span class="number">8</span>; j++)</span><br><span class="line">			<span class="keyword">if</span> (s[j] &gt; s[j - <span class="number">1</span>])</span><br><span class="line">				f = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> j = i - <span class="number">1</span>; j &gt;= <span class="number">1</span>; j--)</span><br><span class="line">			<span class="keyword">if</span> (s[j] &gt; s[j + <span class="number">1</span>])</span><br><span class="line">				f = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">if</span> (f)</span><br><span class="line">			<span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">bool</span> <span class="title">isleap</span><span class="params">(<span class="type">int</span> x)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">return</span> (x % <span class="number">4</span> == <span class="number">0</span> &amp;&amp; x % <span class="number">100</span> != <span class="number">0</span>) || (x % <span class="number">400</span> == <span class="number">0</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">solve</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>, s + <span class="number">1</span>), <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>, t + <span class="number">1</span>);</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= <span class="number">4</span>; i++)</span><br><span class="line">		y[<span class="number">0</span>] = y[<span class="number">0</span>] * <span class="number">10</span> + s[i] - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">5</span>; i &lt;= <span class="number">6</span>; i++)</span><br><span class="line">		m[<span class="number">0</span>] = m[<span class="number">0</span>] * <span class="number">10</span> + s[i] - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">7</span>; i &lt;= <span class="number">8</span>; i++)</span><br><span class="line">		d[<span class="number">0</span>] = d[<span class="number">0</span>] * <span class="number">10</span> + s[i] - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= <span class="number">4</span>; i++)</span><br><span class="line">		y[<span class="number">1</span>] = y[<span class="number">1</span>] * <span class="number">10</span> + t[i] - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">5</span>; i &lt;= <span class="number">6</span>; i++)</span><br><span class="line">		m[<span class="number">1</span>] = m[<span class="number">1</span>] * <span class="number">10</span> + t[i] - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">7</span>; i &lt;= <span class="number">8</span>; i++)</span><br><span class="line">		d[<span class="number">1</span>] = d[<span class="number">1</span>] * <span class="number">10</span> + t[i] - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">	<span class="type">int</span> ans = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span> (y[<span class="number">0</span>] != y[<span class="number">1</span>] || m[<span class="number">0</span>] != m[<span class="number">1</span>] || d[<span class="number">0</span>] != d[<span class="number">1</span>])</span><br><span class="line">	&#123;</span><br><span class="line">		ans += <span class="built_in">check</span>(y[<span class="number">0</span>], m[<span class="number">0</span>], d[<span class="number">0</span>]);</span><br><span class="line">		d[<span class="number">0</span>]++;</span><br><span class="line">		<span class="keyword">if</span> (d[<span class="number">0</span>] &gt; mx[m[<span class="number">0</span>]] + (m[<span class="number">0</span>] == <span class="number">2</span> &amp;&amp; <span class="built_in">isleap</span>(y[<span class="number">0</span>])))</span><br><span class="line">			m[<span class="number">0</span>]++, d[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">		<span class="keyword">if</span> (m[<span class="number">0</span>] &gt; <span class="number">12</span>)</span><br><span class="line">			m[<span class="number">0</span>] = <span class="number">1</span>, y[<span class="number">0</span>]++;</span><br><span class="line">	&#125;</span><br><span class="line">	ans += <span class="built_in">check</span>(y[<span class="number">1</span>], m[<span class="number">1</span>], d[<span class="number">1</span>]);</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, ans);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="type">int</span> t = <span class="number">1</span>, cnt = <span class="number">1</span>;</span><br><span class="line">	<span class="keyword">while</span> (t--)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">solve</span>();</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="E-单词游戏"><a href="#E-单词游戏" class="headerlink" title="E 单词游戏"></a>E 单词游戏</h2><p><img src="/.io//image-20230922101517436.png" alt="image-20230922101517436"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="type">int</span> a[<span class="number">600000</span>][<span class="number">3</span>];</span><br><span class="line"><span class="type">char</span> s[<span class="number">10</span>];</span><br><span class="line"><span class="type">int</span> ans[<span class="number">3</span>];</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">tr</span><span class="params">(<span class="type">char</span> s[])</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="type">int</span> res=<span class="number">0</span>;</span><br><span class="line">	<span class="type">int</span> len=<span class="built_in">strlen</span>(s);</span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;len;i++)</span><br><span class="line">	&#123;</span><br><span class="line">		res=res*<span class="number">27</span>+s[i]-<span class="string">&#x27;a&#x27;</span>+<span class="number">1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="type">int</span> t,n;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;t);</span><br><span class="line">	<span class="keyword">while</span>(t--)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">memset</span>(a,<span class="number">0</span>,<span class="built_in">sizeof</span>(a));</span><br><span class="line">		<span class="built_in">memset</span>(ans,<span class="number">0</span>,<span class="built_in">sizeof</span>(ans));</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;n);</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>;j&lt;<span class="number">3</span>;j++)</span><br><span class="line">		&#123;</span><br><span class="line">			<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;n;i++)</span><br><span class="line">			&#123;</span><br><span class="line">				<span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,s);</span><br><span class="line">				a[<span class="built_in">tr</span>(s)][j]++;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;<span class="number">27</span>*<span class="number">27</span>*<span class="number">27</span>*<span class="number">27</span>;i++)</span><br><span class="line">		&#123;</span><br><span class="line">			<span class="keyword">if</span>(a[i][<span class="number">0</span>]&amp;&amp;a[i][<span class="number">1</span>]&amp;&amp;a[i][<span class="number">2</span>])</span><br><span class="line">			&#123;</span><br><span class="line">				<span class="keyword">continue</span>;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(a[i][<span class="number">0</span>]&amp;&amp;a[i][<span class="number">1</span>])</span><br><span class="line">			&#123;</span><br><span class="line">				ans[<span class="number">0</span>]++;</span><br><span class="line">				ans[<span class="number">1</span>]++;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(a[i][<span class="number">0</span>]&amp;&amp;a[i][<span class="number">2</span>])</span><br><span class="line">			&#123;</span><br><span class="line">				ans[<span class="number">0</span>]++;</span><br><span class="line">				ans[<span class="number">2</span>]++;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(a[i][<span class="number">1</span>]&amp;&amp;a[i][<span class="number">2</span>])</span><br><span class="line">			&#123;</span><br><span class="line">				ans[<span class="number">1</span>]++;</span><br><span class="line">				ans[<span class="number">2</span>]++;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(a[i][<span class="number">0</span>])</span><br><span class="line">			&#123;</span><br><span class="line">				ans[<span class="number">0</span>]+=<span class="number">3</span>;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(a[i][<span class="number">1</span>])</span><br><span class="line">			&#123;</span><br><span class="line">				ans[<span class="number">1</span>]+=<span class="number">3</span>;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(a[i][<span class="number">2</span>])</span><br><span class="line">			&#123;</span><br><span class="line">				ans[<span class="number">2</span>]+=<span class="number">3</span>;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;<span class="number">3</span>;i++)</span><br><span class="line">		&#123;</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>,ans[i]);</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">puts</span>(<span class="string">&quot;&quot;</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>


<h2 id="逆序k倍对"><a href="#逆序k倍对" class="headerlink" title="逆序k倍对"></a>逆序k倍对</h2><p><img src="/.io//image-20230922102005428.png" alt="image-20230922102005428"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="type">int</span> a[<span class="number">1000002</span>], n, k, num;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">long</span> <span class="type">long</span> <span class="title">reversePairsRecursive</span><span class="params">(<span class="type">int</span>* nums, <span class="type">int</span> left, <span class="type">int</span> right)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (left == right) &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">	&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">		<span class="type">int</span> mid = (left + right) / <span class="number">2</span>;</span><br><span class="line">		<span class="type">int</span> n1 = <span class="built_in">reversePairsRecursive</span>(nums, left, mid);</span><br><span class="line">		<span class="type">int</span> n2 = <span class="built_in">reversePairsRecursive</span>(nums, mid + <span class="number">1</span>, right);</span><br><span class="line">		<span class="type">long</span> <span class="type">long</span> ret = n1 + n2;</span><br><span class="line"></span><br><span class="line">		<span class="type">int</span> i = left;</span><br><span class="line">		<span class="type">int</span> j = mid + <span class="number">1</span>;</span><br><span class="line">		<span class="keyword">while</span> (i &lt;= mid) &#123;</span><br><span class="line">			<span class="keyword">while</span> (j &lt;= right &amp;&amp; (<span class="type">long</span> <span class="type">long</span>)nums[i] &gt; k * (<span class="type">long</span> <span class="type">long</span>)nums[j]) j++;</span><br><span class="line">			ret += (j - mid - <span class="number">1</span>) ;</span><br><span class="line">			i++;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		<span class="type">int</span> sorted[right - left + <span class="number">1</span>];</span><br><span class="line">		<span class="type">int</span> p1 = left, p2 = mid + <span class="number">1</span>;</span><br><span class="line">		<span class="type">int</span> p = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">while</span> (p1 &lt;= mid || p2 &lt;= right) &#123;</span><br><span class="line">			<span class="keyword">if</span> (p1 &gt; mid) &#123;</span><br><span class="line">				sorted[p++] = nums[p2++];</span><br><span class="line">			&#125; <span class="keyword">else</span> <span class="keyword">if</span> (p2 &gt; right) &#123;</span><br><span class="line">				sorted[p++] = nums[p1++];</span><br><span class="line">			&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">				<span class="keyword">if</span> (nums[p1] &lt; nums[p2]) &#123;</span><br><span class="line">					sorted[p++] = nums[p1++];</span><br><span class="line">				&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">					sorted[p++] = nums[p2++];</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; right - left + <span class="number">1</span>; i++) &#123;</span><br><span class="line">			nums[left + i] = sorted[i];</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> ret;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">reversePairs</span><span class="params">(<span class="type">int</span>* nums, <span class="type">int</span> numsSize)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (numsSize == <span class="number">0</span>) &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="built_in">reversePairsRecursive</span>(nums, <span class="number">0</span>, numsSize - <span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d %d&quot;</span>,&amp;n,&amp;k);</span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; n ; i++) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;a[i]);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;%lld\n&quot;</span>,<span class="built_in">reversePairs</span>(a,n));</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h1 id="E1"><a href="#E1" class="headerlink" title="E1"></a>E1</h1><h2 id="A-你还记得我嘛-多项式加法"><a href="#A-你还记得我嘛-多项式加法" class="headerlink" title="A 你还记得我嘛~(多项式加法)"></a>A 你还记得我嘛~(多项式加法)</h2><p><img src="/.io//image-20230922103338426.png" alt="image-20230922103338426"></p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> maxn 200086</span></span><br><span class="line"></span><br><span class="line"><span class="type">int</span> t, n, m, k;</span><br><span class="line"><span class="type">int</span> a[maxn], A[maxn], b[maxn], B[maxn], c[maxn], C[maxn];</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> <span class="title function_">main</span><span class="params">()</span></span><br><span class="line">&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t);</span><br><span class="line">	<span class="keyword">while</span> (t--)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;n);</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i++)</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;a[i]);</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i++)</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;A[i]);</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;m);</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= m; i++)</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;b[i]);</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= m; i++)</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;B[i]);</span><br><span class="line">		<span class="type">int</span> posa = <span class="number">1</span>, posb = <span class="number">1</span>;</span><br><span class="line">		k = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">while</span> (posa &lt;= n || posb &lt;= m)</span><br><span class="line">		&#123;</span><br><span class="line">			<span class="keyword">if</span> (posa &gt; n)</span><br><span class="line">				c[++k] = b[posb], C[k] = B[posb], posb++;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span> (posb &gt; m)</span><br><span class="line">				c[++k] = a[posa], C[k] = A[posa], posa++;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span> (A[posa] == B[posb])</span><br><span class="line">				c[++k] = a[posa] + b[posb], C[k] = A[posa], posa++, posb++;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span> (A[posa] &lt; B[posb])</span><br><span class="line">				c[++k] = a[posa], C[k] = A[posa], posa++;</span><br><span class="line">			<span class="keyword">else</span></span><br><span class="line">				c[++k] = b[posb], C[k] = B[posb], posb++;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, k);</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= k; i++)</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, c[i]);</span><br><span class="line">		<span class="built_in">puts</span>(<span class="string">&quot;&quot;</span>);</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= k; i++)</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, C[i]);</span><br><span class="line">		<span class="built_in">puts</span>(<span class="string">&quot;&quot;</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="B-n次方的和"><a href="#B-n次方的和" class="headerlink" title="B n次方的和"></a>B n次方的和</h2><p><img src="/.io//image-20230922104158887.png" alt="image-20230922104158887"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;math.h&gt;</span></span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> t;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;t);</span><br><span class="line">	<span class="keyword">while</span>(t--) &#123;</span><br><span class="line">		<span class="type">int</span> k, z, index = <span class="number">0</span>;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;z,&amp;k);</span><br><span class="line">		<span class="keyword">if</span> (k &gt; <span class="number">2</span>)</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;0\n&quot;</span>);</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span>( k == <span class="number">1</span>)</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, z<span class="number">-1</span>);</span><br><span class="line">		<span class="keyword">else</span> &#123;</span><br><span class="line">			<span class="keyword">for</span>(<span class="type">long</span> <span class="type">long</span> i = <span class="number">1</span>; i &lt; z; i++) &#123;</span><br><span class="line">				<span class="type">double</span> j = <span class="built_in">sqrt</span>(<span class="number">1ll</span> * z * z - i * i);</span><br><span class="line">				<span class="keyword">if</span>(j == (<span class="type">int</span>)j) &#123;</span><br><span class="line">					index++;</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>,index);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>

<h2 id="多路归并"><a href="#多路归并" class="headerlink" title="多路归并"></a>多路归并</h2><p><img src="/.io//image-20230922104257685.png" alt="image-20230922104257685"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> maxn 100086</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> t, k, n;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t);</span><br><span class="line">	<span class="keyword">while</span>(t--) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;k, &amp;n);</span><br><span class="line">		<span class="function">vector&lt;<span class="type">int</span>&gt; <span class="title">v</span><span class="params">(k * n)</span></span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; k * n; i++) <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;v[i]);</span><br><span class="line">		<span class="built_in">sort</span>(v.<span class="built_in">begin</span>(), v.<span class="built_in">end</span>());</span><br><span class="line">		<span class="keyword">for</span>(<span class="keyword">auto</span> x : v) <span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, x);</span><br><span class="line">		<span class="built_in">puts</span>(<span class="string">&quot;&quot;</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h2 id="D-随机数"><a href="#D-随机数" class="headerlink" title="D 随机数"></a>D 随机数</h2><p><img src="/.io//image-20230922104542514.png" alt="image-20230922104542514"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> maxn 20000086</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">unsigned</span> seed;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">Rand</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	seed ^= seed &lt;&lt; <span class="number">13</span>;</span><br><span class="line">	seed ^= seed &gt;&gt; <span class="number">7</span>;</span><br><span class="line">	seed ^= seed &lt;&lt; <span class="number">17</span>;</span><br><span class="line">	<span class="keyword">return</span> seed &amp; ((<span class="number">1</span> &lt;&lt; <span class="number">24</span>) - <span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> t, n, a[maxn];</span><br><span class="line"><span class="type">int</span> num[maxn];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t);</span><br><span class="line">	<span class="keyword">while</span>(t--) &#123;</span><br><span class="line">		<span class="built_in">memset</span>(num, <span class="number">0</span>, <span class="built_in">sizeof</span>(num));</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d%u&quot;</span>, &amp;n, &amp;seed);</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i++) a[i] = <span class="built_in">Rand</span>(), num[a[i]]++;</span><br><span class="line">		<span class="type">unsigned</span> ans = <span class="number">0</span>;</span><br><span class="line">		<span class="type">int</span> cnt = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt;= (<span class="number">1</span> &lt;&lt; <span class="number">24</span>) - <span class="number">1</span>; i++) &#123;</span><br><span class="line">			<span class="keyword">while</span>(num[i]--) cnt++, ans += i ^ cnt;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%u\n&quot;</span>, ans);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="组合数"><a href="#组合数" class="headerlink" title="组合数"></a>组合数</h2><p><img src="/.io//image-20230922105924398.png" alt="image-20230922105924398"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> t, n, m;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t);</span><br><span class="line">	<span class="keyword">while</span>(t--) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;n, &amp;m);</span><br><span class="line">		m = <span class="built_in">min</span>(m, n - m);</span><br><span class="line">		<span class="type">long</span> <span class="type">long</span> x = <span class="number">1</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= m &amp;&amp; x &lt;= <span class="number">1e9</span>; i++) x *= n - i + <span class="number">1</span>, x /= i;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, x &lt;= <span class="number">1e9</span> ? x : <span class="number">-1</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="F-莫卡的二叉树魔法"><a href="#F-莫卡的二叉树魔法" class="headerlink" title="F 莫卡的二叉树魔法"></a>F 莫卡的二叉树魔法</h2><p><img src="/.io//image-20230922110108059.png" alt="image-20230922110108059"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> MIN(a,b) a&lt;b?a:b</span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line">vector&lt;<span class="type">int</span>&gt;a[<span class="number">100005</span>];</span><br><span class="line"><span class="type">int</span> b[<span class="number">100005</span>];</span><br><span class="line"><span class="type">bool</span> path[<span class="number">100005</span>];</span><br><span class="line"><span class="type">char</span> s[<span class="number">100010</span>];</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">dfs</span><span class="params">(<span class="type">int</span> u)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(a[u].<span class="built_in">empty</span>()) &#123;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;a[u].<span class="built_in">size</span>(); i++) &#123;</span><br><span class="line">		b[a[u][i]]^=b[u];</span><br><span class="line">		<span class="built_in">dfs</span>(a[u][i]);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> n,q;</span><br><span class="line">	<span class="type">int</span> x;</span><br><span class="line">	<span class="type">int</span> T;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;T);</span><br><span class="line">	<span class="keyword">while</span>(T--) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;n);</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i++) a[i].<span class="built_in">clear</span>(), b[i] = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2</span>; i&lt;=n; i++) &#123;</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;x);</span><br><span class="line">			a[x].<span class="built_in">push_back</span>(i);</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,s);</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;q);</span><br><span class="line">		<span class="keyword">while</span>(q--) &#123;</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;x);</span><br><span class="line">			b[x]^=<span class="number">1</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">dfs</span>(<span class="number">1</span>);</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>; i&lt;n; i++) &#123;</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%d&quot;</span>,(s[i]-<span class="string">&#x27;0&#x27;</span>)^b[i+<span class="number">1</span>]);</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">puts</span>(<span class="string">&quot;&quot;</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="2的幂"><a href="#2的幂" class="headerlink" title="2的幂"></a>2的幂</h2><p><img src="/.io//image-20230922111251560.png" alt="image-20230922111251560"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> ll;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">55</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> inf = <span class="number">0x3f3f3f3f</span>;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">getint</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="type">char</span> c;</span><br><span class="line">	<span class="type">bool</span> flag = <span class="number">0</span>;</span><br><span class="line">	<span class="type">int</span> num = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span> ((c = <span class="built_in">getchar</span>()) &lt; <span class="string">&#x27;0&#x27;</span> || c &gt; <span class="string">&#x27;9&#x27;</span>)</span><br><span class="line">		<span class="keyword">if</span> (c == <span class="string">&#x27;-&#x27;</span>)</span><br><span class="line">			flag = <span class="number">1</span>;</span><br><span class="line">	<span class="keyword">while</span> (c &gt;= <span class="string">&#x27;0&#x27;</span> &amp;&amp; c &lt;= <span class="string">&#x27;9&#x27;</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		num = num * <span class="number">10</span> + c - <span class="number">48</span>;</span><br><span class="line">		c = <span class="built_in">getchar</span>();</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> flag ? -num : num;</span><br><span class="line">&#125;</span><br><span class="line"><span class="type">int</span> A[N], B[N];</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">match</span><span class="params">(<span class="type">int</span> x, ll target)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="type">int</span> n = <span class="number">0</span>, m = <span class="number">0</span>, i, j;</span><br><span class="line">	<span class="keyword">while</span> (x)</span><br><span class="line">		A[++n] = x % <span class="number">10</span>, x /= <span class="number">10</span>;</span><br><span class="line">	<span class="keyword">while</span> (target)</span><br><span class="line">		B[++m] = target % <span class="number">10</span>, target /= <span class="number">10</span>;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">for</span> (i = m, j = n; i &amp;&amp; j; i--, j--)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">for</span> (; j &amp;&amp; B[i] != A[j]; j--)</span><br><span class="line">			;</span><br><span class="line">		<span class="keyword">if</span> (j &lt;= <span class="number">0</span>)</span><br><span class="line">			<span class="keyword">break</span>;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="type">int</span> delete_num = n - (m - i);</span><br><span class="line">	<span class="type">int</span> add_num = i;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">return</span> delete_num + add_num;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="type">int</span> T = <span class="built_in">getint</span>();</span><br><span class="line">	<span class="keyword">while</span> (T--)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="type">int</span> n = <span class="built_in">getint</span>(), ans = inf;</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt;= <span class="number">60</span>; i++)</span><br><span class="line">			ans = <span class="built_in">min</span>(ans, <span class="built_in">match</span>(n, <span class="number">1ll</span> &lt;&lt; i));</span><br><span class="line">		cout &lt;&lt; ans &lt;&lt; endl;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="I-XIAO7-的地图"><a href="#I-XIAO7-的地图" class="headerlink" title="I XIAO7 的地图"></a>I XIAO7 的地图</h2><p><img src="/.io//image-20230922112139921.png" alt="image-20230922112139921"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> index_list[<span class="number">11</span>] = &#123;<span class="number">0</span>&#125;;</span><br><span class="line"><span class="type">int</span> box[<span class="number">2047</span>][<span class="number">2047</span>] = &#123;&#123;<span class="number">0</span>&#125;&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">//turn为1表示顺时针旋转90°， turn为-1表示逆时针旋转90°， turn为0表示不旋转</span></span><br><span class="line">vector&lt;pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt;&gt; <span class="built_in">draw_map</span>(<span class="type">int</span> x, <span class="type">int</span> y, <span class="type">int</span> index, <span class="type">int</span> turn) &#123;</span><br><span class="line">    vector&lt;pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt;&gt; draw;</span><br><span class="line">    <span class="comment">//添加点</span></span><br><span class="line">    <span class="keyword">if</span> (index == <span class="number">1</span>) &#123;</span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + <span class="number">0</span>,y + <span class="number">0</span>));</span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + <span class="number">1</span>,y + <span class="number">0</span>));</span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + <span class="number">2</span>,y + <span class="number">0</span>));</span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + <span class="number">2</span>,y + <span class="number">1</span>));</span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + <span class="number">2</span>,y + <span class="number">2</span>));</span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + <span class="number">1</span>,y + <span class="number">2</span>));</span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + <span class="number">0</span>,y + <span class="number">2</span>));</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span> &#123;</span><br><span class="line">        <span class="comment">//递归绘制四个子图</span></span><br><span class="line">        vector&lt;pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt;&gt; draw1 = <span class="built_in">draw_map</span>(x, y, index - <span class="number">1</span>, <span class="number">1</span>);</span><br><span class="line">        vector&lt;pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt;&gt; draw2 = <span class="built_in">draw_map</span>(x + index_list[index<span class="number">-1</span>] + <span class="number">1</span>, y, index - <span class="number">1</span>, <span class="number">0</span>);</span><br><span class="line">        vector&lt;pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt;&gt; draw3 = <span class="built_in">draw_map</span>(x, y + index_list[index<span class="number">-1</span>] + <span class="number">1</span>, index - <span class="number">1</span>, <span class="number">-1</span>);</span><br><span class="line">        vector&lt;pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt;&gt; draw4 = <span class="built_in">draw_map</span>(x + index_list[index<span class="number">-1</span>] + <span class="number">1</span>, y + index_list[index<span class="number">-1</span>] + <span class="number">1</span>, index - <span class="number">1</span>, <span class="number">0</span>);</span><br><span class="line">        draw.<span class="built_in">insert</span>(draw.<span class="built_in">end</span>(), draw1.<span class="built_in">begin</span>(), draw1.<span class="built_in">end</span>());</span><br><span class="line">        draw.<span class="built_in">insert</span>(draw.<span class="built_in">end</span>(), draw2.<span class="built_in">begin</span>(), draw2.<span class="built_in">end</span>());</span><br><span class="line">        draw.<span class="built_in">insert</span>(draw.<span class="built_in">end</span>(), draw3.<span class="built_in">begin</span>(), draw3.<span class="built_in">end</span>());</span><br><span class="line">        draw.<span class="built_in">insert</span>(draw.<span class="built_in">end</span>(), draw4.<span class="built_in">begin</span>(), draw4.<span class="built_in">end</span>());</span><br><span class="line">        <span class="comment">//绘制三个连接点</span></span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + index_list[index<span class="number">-1</span>],y));</span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + index_list[index<span class="number">-1</span>] + <span class="number">1</span>,y + index_list[index<span class="number">-1</span>]));</span><br><span class="line">        draw.<span class="built_in">push_back</span>(<span class="built_in">pair</span>&lt;<span class="type">int</span>, <span class="type">int</span>&gt;(x + index_list[index<span class="number">-1</span>],y + <span class="number">2</span> * index_list[index<span class="number">-1</span>]));</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//处理旋转(瞬时针旋转90°)</span></span><br><span class="line">    <span class="keyword">if</span> (turn == <span class="number">1</span> || turn == <span class="number">-1</span>) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">auto</span> &amp;it:draw) &#123;</span><br><span class="line">            <span class="type">int</span> off_x = it.first - x;</span><br><span class="line">            <span class="type">int</span> off_y = it.second - y;</span><br><span class="line">            it.first = x + off_y;</span><br><span class="line">            it.second = y + off_x;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//上下对称</span></span><br><span class="line">    <span class="keyword">if</span> (turn == <span class="number">-1</span>) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">auto</span> &amp;it:draw) &#123;</span><br><span class="line">            <span class="type">int</span> off_y = it.second - y;</span><br><span class="line">            it.second = y + index_list[index] - <span class="number">1</span> - off_y;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> draw;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="type">int</span> n;</span><br><span class="line">    cin &gt;&gt; n;</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt; <span class="number">11</span>; i++) &#123;</span><br><span class="line">        index_list[i] = <span class="built_in">pow</span>(<span class="number">2</span>, i + <span class="number">1</span>) - <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    vector&lt;pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt;&gt; draw_final = <span class="built_in">draw_map</span>(<span class="number">0</span>,<span class="number">0</span>,n,<span class="number">0</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">auto</span> it:draw_final) &#123;</span><br><span class="line">        box[it.second][it.first] = <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//绘图</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; <span class="built_in">pow</span>(<span class="number">2</span>,n + <span class="number">1</span>) - <span class="number">1</span>; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; <span class="built_in">pow</span>(<span class="number">2</span>, n + <span class="number">1</span>) - <span class="number">1</span>; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (box[i][j] == <span class="number">1</span>) &#123;</span><br><span class="line">                cout &lt;&lt; <span class="string">&quot;*&quot;</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span> &#123;</span><br><span class="line">                cout &lt;&lt; <span class="string">&quot; &quot;</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        cout &lt;&lt; endl;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h1 id="C2"><a href="#C2" class="headerlink" title="C2"></a>C2</h1><h2 id="平面最近点对"><a href="#平面最近点对" class="headerlink" title="平面最近点对"></a>平面最近点对</h2><p><img src="/.io//image-20230922142257679.png" alt="image-20230922142257679"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> maxn 1005</span></span><br><span class="line"><span class="keyword">using</span> ll = <span class="type">long</span> <span class="type">long</span>;</span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="type">int</span> t, n, x[maxn], y[maxn];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;t);</span><br><span class="line">	<span class="keyword">while</span>(t--) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;n);</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i++) <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, x + i), <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, y + i);</span><br><span class="line">		<span class="type">int</span> ans = <span class="number">200000</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i++) </span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>; j &lt; i; j++) </span><br><span class="line">                ans = <span class="built_in">min</span>(ans, <span class="built_in">max</span>(<span class="built_in">abs</span>(x[i] - x[j]), <span class="built_in">abs</span>(y[i] - y[j])));</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, ans);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>

<h2 id="B-最大堆的实现"><a href="#B-最大堆的实现" class="headerlink" title="B 最大堆的实现"></a>B 最大堆的实现</h2><p><img src="/.io//image-20230922142531892.png" alt="image-20230922142531892"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> maxn 1000005</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> inf 0x3f3f3f3f</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> ls(x) (x &lt;&lt; 1)</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> rs(x) (x &lt;&lt; 1 | 1)</span></span><br><span class="line"></span><br><span class="line"><span class="type">int</span> n, sz, a[maxn];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">swap</span><span class="params">(<span class="type">int</span> *a, <span class="type">int</span> *b)</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> t = *a;</span><br><span class="line">	*a = *b, *b = t;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">maxHeapify</span><span class="params">(<span class="type">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> l = <span class="built_in">ls</span>(x), r = <span class="built_in">rs</span>(x), larg;</span><br><span class="line">	<span class="keyword">if</span>(l &lt;= sz &amp;&amp; a[l] &gt; a[x]) larg = l;</span><br><span class="line">	<span class="keyword">else</span> larg = x;</span><br><span class="line">	<span class="keyword">if</span>(r &lt;= sz &amp;&amp; a[r] &gt; a[larg]) larg = r;</span><br><span class="line">	<span class="keyword">if</span>(larg != x) <span class="built_in">swap</span>(&amp;a[x], &amp;a[larg]), <span class="built_in">maxHeapify</span>(larg);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">increaseKey</span><span class="params">(<span class="type">int</span> i, <span class="type">int</span> key)</span> </span>&#123;</span><br><span class="line">	a[i] = key;</span><br><span class="line">	<span class="keyword">while</span>(i &gt; <span class="number">1</span> &amp;&amp; a[i / <span class="number">2</span>] &lt; a[i]) &#123;</span><br><span class="line">		<span class="built_in">swap</span>(&amp;a[i / <span class="number">2</span>], &amp;a[i]);</span><br><span class="line">		i = i / <span class="number">2</span>;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">insert</span><span class="params">(<span class="type">int</span> x)</span> </span>&#123;</span><br><span class="line">	sz += <span class="number">1</span>;</span><br><span class="line">	a[sz] = -inf;</span><br><span class="line">	<span class="built_in">increaseKey</span>(sz, x);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">top</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">return</span> a[<span class="number">1</span>];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">pop</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(sz &lt; <span class="number">1</span>) <span class="built_in">exit</span>(<span class="number">1</span>);</span><br><span class="line">	a[<span class="number">1</span>] = a[sz];</span><br><span class="line">	sz -= <span class="number">1</span>;</span><br><span class="line">	<span class="built_in">maxHeapify</span>(<span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;n);</span><br><span class="line">	<span class="type">int</span> i;</span><br><span class="line">	<span class="keyword">for</span>(i = <span class="number">1</span>; i &lt;= n; i++) &#123;</span><br><span class="line">		<span class="type">int</span> op, x;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;op);</span><br><span class="line">		<span class="keyword">if</span>(op == <span class="number">1</span>) &#123;</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;x);</span><br><span class="line">			<span class="built_in">insert</span>(x);</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(op == <span class="number">2</span>) <span class="built_in">pop</span>();</span><br><span class="line">		<span class="keyword">if</span>(op == <span class="number">3</span>) <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, <span class="built_in">top</span>());</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">while</span>(sz) &#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, <span class="built_in">top</span>()), <span class="built_in">pop</span>();</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h1 id="E2"><a href="#E2" class="headerlink" title="E2"></a>E2</h1><h2 id="A-简单的可删堆"><a href="#A-简单的可删堆" class="headerlink" title="A 简单的可删堆"></a>A 简单的可删堆</h2><p><img src="/.io//image-20230922144420311.png" alt="image-20230922144420311"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;string.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;math.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;ctype.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> pi acos(-1)</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> inf 2147483647</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> llinf 9223372036854775807</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> MIN(a,b) (a&lt;b?a:b)</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> MAX(a,b) (a&gt;b?a:b)</span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> N 200010</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">swap</span><span class="params">(<span class="type">int</span> *a,<span class="type">int</span> *b)</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> t=*a;</span><br><span class="line">	*a=*b;</span><br><span class="line">	*b=t;</span><br><span class="line">&#125;</span><br><span class="line"><span class="type">int</span> heap_size=<span class="number">0</span>;</span><br><span class="line"><span class="type">int</span> heap[N];</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> heapDel_size=<span class="number">0</span>;</span><br><span class="line"><span class="type">int</span> heapDel[N];</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">put</span><span class="params">(<span class="type">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> now,next,res;</span><br><span class="line">	heap[++heap_size]=x;</span><br><span class="line">	now=heap_size;</span><br><span class="line">	<span class="keyword">while</span>(now&gt;<span class="number">1</span>) &#123;</span><br><span class="line">		next=now&gt;&gt;<span class="number">1</span>;</span><br><span class="line">		<span class="keyword">if</span>(heap[now]&gt;=heap[next]) &#123;</span><br><span class="line">			<span class="keyword">return</span>;</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			<span class="built_in">swap</span>(&amp;heap[now],&amp;heap[next]);</span><br><span class="line">			now=next;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">get</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(heap_size&lt;<span class="number">1</span>)<span class="built_in">exit</span>(<span class="number">-1</span>);</span><br><span class="line">	<span class="keyword">return</span> heap[<span class="number">1</span>];</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">del</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(heap_size&lt;<span class="number">1</span>)<span class="built_in">exit</span>(<span class="number">-1</span>);</span><br><span class="line">	<span class="type">int</span> res=heap[<span class="number">1</span>];</span><br><span class="line">	heap[<span class="number">1</span>]=heap[heap_size--];</span><br><span class="line">	<span class="type">int</span> now=<span class="number">1</span>,next;</span><br><span class="line">	<span class="keyword">while</span>(now*<span class="number">2</span>&lt;=heap_size) &#123;</span><br><span class="line">		next=now*<span class="number">2</span>;</span><br><span class="line">		<span class="keyword">if</span>(next&lt;heap_size&amp;&amp;heap[next+<span class="number">1</span>]&lt;heap[next]) &#123;</span><br><span class="line">			next++;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(heap[now]&lt;=heap[next]) &#123;</span><br><span class="line">			<span class="keyword">return</span> res;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">swap</span>(&amp;heap[now],&amp;heap[next]);</span><br><span class="line">		now=next;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">putDel</span><span class="params">(<span class="type">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> now,next,res;</span><br><span class="line">	heapDel[++heapDel_size]=x;</span><br><span class="line">	now=heapDel_size;</span><br><span class="line">	<span class="keyword">while</span>(now&gt;<span class="number">1</span>) &#123;</span><br><span class="line">		next=now&gt;&gt;<span class="number">1</span>;</span><br><span class="line">		<span class="keyword">if</span>(heapDel[now]&gt;=heapDel[next]) &#123;</span><br><span class="line">			<span class="keyword">return</span>;</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			<span class="built_in">swap</span>(&amp;heapDel[now],&amp;heapDel[next]);</span><br><span class="line">			now=next;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">getDel</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(heapDel_size&lt;<span class="number">1</span>)<span class="keyword">return</span> <span class="number">-2</span>;</span><br><span class="line">	<span class="keyword">return</span> heapDel[<span class="number">1</span>];</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">delDel</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> res=heapDel[<span class="number">1</span>];</span><br><span class="line">	heapDel[<span class="number">1</span>]=heapDel[heapDel_size--];</span><br><span class="line">	<span class="type">int</span> now=<span class="number">1</span>,next;</span><br><span class="line">	<span class="keyword">while</span>(now*<span class="number">2</span>&lt;=heapDel_size) &#123;</span><br><span class="line">		next=now*<span class="number">2</span>;</span><br><span class="line">		<span class="keyword">if</span>(next&lt;heapDel_size&amp;&amp;heapDel[next+<span class="number">1</span>]&lt;heapDel[next]) &#123;</span><br><span class="line">			next++;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(heapDel[now]&lt;=heapDel[next]) &#123;</span><br><span class="line">			<span class="keyword">return</span> res;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">swap</span>(&amp;heapDel[now],&amp;heapDel[next]);</span><br><span class="line">		now=next;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> n,op,x;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;n);</span><br><span class="line">	<span class="keyword">while</span>(n--) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;op);</span><br><span class="line">		<span class="keyword">if</span>(op==<span class="number">1</span>) &#123;</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;x);</span><br><span class="line">			<span class="built_in">put</span>(x);</span><br><span class="line">		&#125; <span class="keyword">else</span> <span class="keyword">if</span>(op==<span class="number">2</span>) &#123;</span><br><span class="line">			<span class="keyword">while</span>(<span class="built_in">get</span>()==<span class="built_in">getDel</span>()) &#123;</span><br><span class="line">				<span class="built_in">del</span>();</span><br><span class="line">				<span class="built_in">delDel</span>();</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="built_in">del</span>();</span><br><span class="line">		&#125; <span class="keyword">else</span> <span class="keyword">if</span>(op==<span class="number">3</span>) &#123;</span><br><span class="line">			<span class="keyword">while</span>(<span class="built_in">get</span>()==<span class="built_in">getDel</span>()) &#123;</span><br><span class="line">				<span class="built_in">del</span>();</span><br><span class="line">				<span class="built_in">delDel</span>();</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>,<span class="built_in">get</span>());</span><br><span class="line">		&#125; <span class="keyword">else</span> <span class="keyword">if</span>(op==<span class="number">4</span>) &#123;</span><br><span class="line">			<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;x);</span><br><span class="line">			<span class="built_in">putDel</span>(x);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">while</span>(heap_size&gt;<span class="number">0</span>) &#123;</span><br><span class="line">		<span class="keyword">if</span>(<span class="built_in">get</span>()==<span class="built_in">getDel</span>()) &#123;</span><br><span class="line">			<span class="built_in">del</span>();</span><br><span class="line">			<span class="built_in">delDel</span>();</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>,<span class="built_in">del</span>());</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="B-递归铺瓷砖"><a href="#B-递归铺瓷砖" class="headerlink" title="B 递归铺瓷砖"></a>B 递归铺瓷砖</h2><p><img src="/.io//image-20230922145722701.png" alt="image-20230922145722701"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span> (i = <span class="number">6</span>; i &lt; M; i++)</span><br><span class="line">	&#123;</span><br><span class="line">		result[i] = (result[i - <span class="number">1</span>] + result[i - <span class="number">2</span>] + <span class="number">4</span> * result[i - <span class="number">3</span>] + <span class="number">2</span> * result[i - <span class="number">4</span>] + <span class="number">2</span> * sum[i - <span class="number">3</span>]) % MOD;</span><br><span class="line">    <span class="comment">// sum的来源：铺满长度为 n-i (i &gt; 4)的地板后，可以用棕色弯块，拼接i-3个绿色短块，再拼接灰色弯块或黄绿色弯块；或者使用粉色弯块，拼接i-3个绿色短块，再拼接灰色弯块或黄绿色弯块</span></span><br><span class="line">		sum[i] = (sum[i - <span class="number">1</span>] + result[i]) % MOD;</span><br><span class="line">	&#125;</span><br></pre></td></tr></table></figure>



<h2 id="C-子集"><a href="#C-子集" class="headerlink" title="C 子集"></a>C 子集</h2><p><img src="/.io//image-20230922151222239.png" alt="image-20230922151222239"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> t, n, m;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;t);</span><br><span class="line">	<span class="keyword">while</span>(t--)&#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;n, &amp;m);</span><br><span class="line">		<span class="type">int</span> ans = <span class="number">1</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i &lt;= (n + <span class="number">1</span>) / <span class="number">2</span>;i++) ans *= n - i + <span class="number">1</span>, ans /= i;</span><br><span class="line">		<span class="keyword">if</span>(ans &lt; m)&#123;</span><br><span class="line">			<span class="built_in">puts</span>(<span class="string">&quot;-1&quot;</span>);</span><br><span class="line">			<span class="keyword">continue</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>;i &lt; (<span class="number">1</span> &lt;&lt; n) &amp;&amp; m;i++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(__builtin_popcount(i) == (n + <span class="number">1</span>) / <span class="number">2</span>)&#123;</span><br><span class="line">				m--;</span><br><span class="line">				<span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, (n + <span class="number">1</span>) / <span class="number">2</span>);</span><br><span class="line">				<span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">0</span>;j &lt; n;j++) </span><br><span class="line">                    <span class="keyword">if</span>(i &amp; (<span class="number">1</span> &lt;&lt; j)) </span><br><span class="line">                        <span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, j + <span class="number">1</span>);</span><br><span class="line">                <span class="built_in">puts</span>(<span class="string">&quot;&quot;</span>); </span><br><span class="line">            &#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>

<h2 id="汉诺塔"><a href="#汉诺塔" class="headerlink" title="汉诺塔"></a>汉诺塔</h2><p><img src="/.io//image-20230922151900640.png" alt="image-20230922151900640"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> inf 1e18</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> maxn 20005</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> ll;</span><br><span class="line"><span class="keyword">typedef</span> <span class="type">unsigned</span> <span class="type">long</span> <span class="type">long</span> ull;</span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="type">const</span> ll mod = <span class="number">998244353</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">double</span> eps = <span class="number">1e-4</span>;</span><br><span class="line"><span class="function"><span class="keyword">inline</span> ll <span class="title">read</span><span class="params">()</span></span>&#123;</span><br><span class="line">    ll x = <span class="number">0</span>, f = <span class="number">1</span>;<span class="type">char</span> ch = <span class="built_in">getchar</span>();</span><br><span class="line">    <span class="keyword">while</span>(ch &gt; <span class="string">&#x27;9&#x27;</span> || ch &lt; <span class="string">&#x27;0&#x27;</span>)&#123;<span class="keyword">if</span>(ch == <span class="string">&#x27;-&#x27;</span>) f = <span class="number">-1</span>;ch = <span class="built_in">getchar</span>();&#125;</span><br><span class="line">    <span class="keyword">while</span>(ch &gt;= <span class="string">&#x27;0&#x27;</span> &amp;&amp; ch &lt;= <span class="string">&#x27;9&#x27;</span>)&#123;x = x * <span class="number">10</span> + ch -<span class="string">&#x27;0&#x27;</span>;ch = <span class="built_in">getchar</span>();&#125;</span><br><span class="line">    <span class="keyword">return</span> x * f;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> n;</span><br><span class="line"><span class="type">char</span> s[maxn];</span><br><span class="line"></span><br><span class="line"><span class="type">char</span> pan[<span class="number">5</span>] = &#123;<span class="string">&#x27; &#x27;</span>, <span class="string">&#x27;A&#x27;</span>, <span class="string">&#x27;B&#x27;</span>, <span class="string">&#x27;C&#x27;</span>&#125;;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">solve</span><span class="params">(<span class="type">int</span> n, <span class="type">int</span> now, <span class="type">int</span> to)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(n == <span class="number">1</span>)&#123;</span><br><span class="line">        <span class="keyword">if</span>(to == now % <span class="number">3</span> + <span class="number">1</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span>(s[n] == <span class="string">&#x27;r&#x27;</span>) <span class="built_in">printf</span>(<span class="string">&quot;move 1 from %c to %c\n&quot;</span>, pan[now], pan[to]);</span><br><span class="line">            <span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">&quot;move 1 from %c to %c\n&quot;</span>, pan[now], pan[<span class="number">6</span> - now - to]), <span class="built_in">printf</span>(<span class="string">&quot;move 1 from %c to %c\n&quot;</span>, pan[<span class="number">6</span> - now - to], pan[to]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="keyword">if</span>(s[n] == <span class="string">&#x27;l&#x27;</span>) <span class="built_in">printf</span>(<span class="string">&quot;move 1 from %c to %c\n&quot;</span>, pan[now], pan[to]);</span><br><span class="line">            <span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">&quot;move 1 from %c to %c\n&quot;</span>, pan[now], pan[<span class="number">6</span> - now - to]), <span class="built_in">printf</span>(<span class="string">&quot;move 1 from %c to %c\n&quot;</span>, pan[<span class="number">6</span> - now - to], pan[to]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(to == now % <span class="number">3</span> + <span class="number">1</span>) &#123;</span><br><span class="line">        <span class="keyword">if</span>(s[n] == <span class="string">&#x27;r&#x27;</span>) <span class="built_in">solve</span>(n - <span class="number">1</span>, now, <span class="number">6</span> - now - to), <span class="built_in">printf</span>(<span class="string">&quot;move %d from %c to %c\n&quot;</span>, n, pan[now], pan[to]), <span class="built_in">solve</span>(n - <span class="number">1</span>, <span class="number">6</span> - now - to, to);</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="built_in">solve</span>(n - <span class="number">1</span>, now, to);</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">&quot;move %d from %c to %c\n&quot;</span>, n, pan[now], pan[<span class="number">6</span> - now - to]);</span><br><span class="line">            <span class="built_in">solve</span>(n - <span class="number">1</span>, to, now);</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">&quot;move %d from %c to %c\n&quot;</span>, n,  pan[<span class="number">6</span> - now - to], pan[to]);</span><br><span class="line">            <span class="built_in">solve</span>(n - <span class="number">1</span>, now, to);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(s[n] == <span class="string">&#x27;l&#x27;</span>) <span class="built_in">solve</span>(n - <span class="number">1</span>, now, <span class="number">6</span> - now - to),<span class="built_in">printf</span>(<span class="string">&quot;move %d from %c to %c\n&quot;</span>, n, pan[now], pan[to]), <span class="built_in">solve</span>(n - <span class="number">1</span>, <span class="number">6</span> - now - to, to);</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="built_in">solve</span>(n - <span class="number">1</span>, now, to);</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">&quot;move %d from %c to %c\n&quot;</span>, n, pan[now], pan[<span class="number">6</span> - now - to]);</span><br><span class="line">            <span class="built_in">solve</span>(n - <span class="number">1</span>, to, now);</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">&quot;move %d from %c to %c\n&quot;</span>, n, pan[<span class="number">6</span> - now - to], pan[to]);</span><br><span class="line">            <span class="built_in">solve</span>(n - <span class="number">1</span>, now, to);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d%s&quot;</span>, &amp;n, s + <span class="number">1</span>) != EOF)&#123;</span><br><span class="line">        <span class="built_in">solve</span>(n, <span class="number">1</span>, <span class="number">3</span>);</span><br><span class="line">        <span class="built_in">puts</span>(<span class="string">&quot;&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h1 id="C7"><a href="#C7" class="headerlink" title="C7"></a>C7</h1><h2 id="B-搬砖问题"><a href="#B-搬砖问题" class="headerlink" title="B 搬砖问题"></a>B 搬砖问题</h2><p><img src="/.io//image-20230922141545470.png" alt="image-20230922141545470"></p>
<p>看了一眼，确信直接贪心就好</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;cstdlib&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;set&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;ctime&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;map&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;assert.h&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> ll;</span><br><span class="line"><span class="keyword">typedef</span> pair&lt;ll, ll&gt; pi;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">100005</span>;</span><br><span class="line"><span class="type">const</span> ll inf = <span class="number">1ll</span> &lt;&lt; <span class="number">60</span>;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">getint</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="type">char</span> c;</span><br><span class="line">	<span class="type">bool</span> flag=<span class="number">0</span>;</span><br><span class="line">	<span class="type">int</span> num=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span>((c=<span class="built_in">getchar</span>())&lt;<span class="string">&#x27;0&#x27;</span>||c&gt;<span class="string">&#x27;9&#x27;</span>)<span class="keyword">if</span>(c==<span class="string">&#x27;-&#x27;</span>)flag=<span class="number">1</span>;</span><br><span class="line">	<span class="keyword">while</span>(c&gt;=<span class="string">&#x27;0&#x27;</span>&amp;&amp;c&lt;=<span class="string">&#x27;9&#x27;</span>) &#123;</span><br><span class="line">		num=num*<span class="number">10</span>+c<span class="number">-48</span>;</span><br><span class="line">		c=<span class="built_in">getchar</span>();</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> flag ? -num : num;</span><br><span class="line">&#125;</span><br><span class="line">pi a[N];</span><br><span class="line">ll t[N];</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">	<span class="type">int</span> n;</span><br><span class="line">	<span class="type">int</span> tt;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;tt);</span><br><span class="line">	<span class="keyword">while</span>(tt--) &#123;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;n);</span><br><span class="line">		<span class="built_in">assert</span>(n &lt;= <span class="number">1e5</span>);</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i ++) &#123;</span><br><span class="line">			a[i].second = <span class="built_in">getint</span>();</span><br><span class="line">			a[i].first = <span class="built_in">getint</span>();</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">sort</span>(a + <span class="number">1</span>, a + n + <span class="number">1</span>);</span><br><span class="line"></span><br><span class="line">		<span class="type">int</span> T = <span class="built_in">getint</span>();</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= T; i ++) &#123;</span><br><span class="line">			t[i] = <span class="built_in">getint</span>();</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">sort</span>(t + <span class="number">1</span>, t + T + <span class="number">1</span>), t[T + <span class="number">1</span>] = inf;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">		ll ans = <span class="number">0</span>, sum = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>, j = <span class="number">1</span>; i &lt;= n; ) &#123;</span><br><span class="line">			<span class="keyword">if</span>(sum + a[i].second &lt;= t[j])  &#123;</span><br><span class="line">				ans += <span class="number">1ll</span> * j * a[i].first * a[i].second;</span><br><span class="line">				sum += a[i].second, i ++;</span><br><span class="line">			&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">				ll m = t[j] - sum;</span><br><span class="line">				a[i].second -= m;</span><br><span class="line">				ans += <span class="number">1ll</span> * j * a[i].first * m;</span><br><span class="line">				sum += m, j ++;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		cout &lt;&lt; ans &lt;&lt; endl;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<h2 id="C-Bellalabella-与中位数"><a href="#C-Bellalabella-与中位数" class="headerlink" title="C Bellalabella 与中位数"></a>C Bellalabella 与中位数</h2><p><img src="/.io//image-20230922135427281.png" alt="image-20230922135427281"></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> inf 0x3f3f3f3f</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> eps 1e-14</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> maxn 1000005</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> ls (tot &lt;&lt; 1)</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> rs (tot &lt;&lt; 1 | 1)</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> PII pair<span class="string">&lt;int, int&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> fi first</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> se second</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> ll;</span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">double</span> ld;</span><br><span class="line"><span class="keyword">typedef</span> <span class="type">unsigned</span> <span class="type">long</span> <span class="type">long</span> ull;</span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="type">const</span> <span class="type">double</span> pi = <span class="built_in">acosl</span>(<span class="number">-1.0L</span>);</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> mod = <span class="number">998244353</span>;</span><br><span class="line"><span class="function"><span class="keyword">inline</span> ll <span class="title">read</span><span class="params">()</span></span>&#123;</span><br><span class="line">    ll x = <span class="number">0</span>, f = <span class="number">1</span>;<span class="type">char</span> ch = <span class="built_in">getchar</span>();</span><br><span class="line">    <span class="keyword">while</span>(ch &gt; <span class="string">&#x27;9&#x27;</span> || ch &lt; <span class="string">&#x27;0&#x27;</span>)&#123;<span class="keyword">if</span>(ch == <span class="string">&#x27;-&#x27;</span>) f = <span class="number">-1</span>;ch = <span class="built_in">getchar</span>();&#125;</span><br><span class="line">    <span class="keyword">while</span>(ch &gt;= <span class="string">&#x27;0&#x27;</span> &amp;&amp; ch &lt;= <span class="string">&#x27;9&#x27;</span>)&#123;x = x * <span class="number">10</span> + ch -<span class="string">&#x27;0&#x27;</span>;ch = <span class="built_in">getchar</span>();&#125;</span><br><span class="line">    <span class="keyword">return</span> x * f;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="type">int</span> n, a[maxn];</span><br><span class="line">priority_queue&lt;<span class="type">int</span>&gt; q;</span><br><span class="line">priority_queue&lt;<span class="type">int</span>, vector&lt;<span class="type">int</span>&gt;, greater&lt;<span class="type">int</span>&gt;&gt; p;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">solve</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="keyword">while</span>(!q.<span class="built_in">empty</span>())q.<span class="built_in">pop</span>();</span><br><span class="line">	<span class="keyword">while</span>(!p.<span class="built_in">empty</span>())p.<span class="built_in">pop</span>();</span><br><span class="line">	n = <span class="built_in">read</span>();</span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</span><br><span class="line">		a[i] = <span class="built_in">read</span>();</span><br><span class="line">		q.<span class="built_in">push</span>(a[i]);</span><br><span class="line">		<span class="keyword">if</span>(i &amp; <span class="number">1</span>)&#123;</span><br><span class="line">			<span class="keyword">while</span>(q.<span class="built_in">size</span>() &gt; p.<span class="built_in">size</span>()) p.<span class="built_in">push</span>(q.<span class="built_in">top</span>()), q.<span class="built_in">pop</span>();</span><br><span class="line">			<span class="keyword">while</span>(q.<span class="built_in">size</span>() &lt; p.<span class="built_in">size</span>()) q.<span class="built_in">push</span>(p.<span class="built_in">top</span>()), p.<span class="built_in">pop</span>();</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, q.<span class="built_in">top</span>());</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">puts</span>(<span class="string">&quot;&quot;</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line"></span><br><span class="line">	<span class="built_in">init</span>();</span><br><span class="line">	<span class="type">int</span> t = <span class="built_in">read</span>();</span><br><span class="line">	<span class="keyword">while</span>(t--)&#123;</span><br><span class="line">		<span class="built_in">solve</span>();</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">   <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>


      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="https://mathieulin.gitee.io/2023/09/21/%E8%A1%A5%E5%85%85%E6%9D%BF%E5%AD%90/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Mathieu Lin">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Mathieu's blog">
      <meta itemprop="description" content="这是一个记载了lzhow传奇的一生的博客">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | Mathieu's blog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2023/09/21/%E8%A1%A5%E5%85%85%E6%9D%BF%E5%AD%90/" class="post-title-link" itemprop="url">未命名</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2023-09-21 12:30:18" itemprop="dateCreated datePublished" datetime="2023-09-21T12:30:18+08:00">2023-09-21</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2023-09-22 16:03:57" itemprop="dateModified" datetime="2023-09-22T16:03:57+08:00">2023-09-22</time>
    </span>

  
  
  <span class="post-meta-item">
    
    <span class="post-meta-item-icon">
      <i class="far fa-comment"></i>
    </span>
    <span class="post-meta-item-text">评论数：</span>
  
    <a title="waline" href="/2023/09/21/%E8%A1%A5%E5%85%85%E6%9D%BF%E5%AD%90/#waline" itemprop="discussionUrl">
      <span class="post-comments-count waline-comment-count" data-path="/2023/09/21/%E8%A1%A5%E5%85%85%E6%9D%BF%E5%AD%90/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h1 id="补充板子"><a href="#补充板子" class="headerlink" title="补充板子"></a>补充板子</h1><h3 id="进制转换"><a href="#进制转换" class="headerlink" title="进制转换"></a>进制转换</h3><h4 id="10进制转2进制"><a href="#10进制转2进制" class="headerlink" title="10进制转2进制"></a>10进制转2进制</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> <span class="title function_">ten_to_two</span><span class="params">()</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="type">int</span> num;</span><br><span class="line">	<span class="type">int</span> temp;</span><br><span class="line">	<span class="type">int</span> i=<span class="number">0</span>;</span><br><span class="line">    <span class="type">int</span> arr[<span class="number">20</span>];</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;请输入一个十进制数：\n&quot;</span>);</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;num);</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">do</span>&#123;</span><br><span class="line">    	temp=num%<span class="number">2</span>;</span><br><span class="line">    	num=num/<span class="number">2</span>;</span><br><span class="line">    	arr[i++]=temp; </span><br><span class="line">    &#125;<span class="keyword">while</span> (num!=<span class="number">0</span>);</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> j = i<span class="number">-1</span>; j&gt;=<span class="number">0</span>; j--)</span><br><span class="line">   		<span class="built_in">printf</span>(<span class="string">&quot;%d&quot;</span>,arr[j]);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h4 id="2进制转10进制"><a href="#2进制转10进制" class="headerlink" title="2进制转10进制"></a>2进制转10进制</h4><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> <span class="title function_">two_to_ten</span><span class="params">()</span> &#123;</span><br><span class="line">	<span class="type">int</span> i, d, a, b, sum = <span class="number">0</span>;</span><br><span class="line">	<span class="type">char</span> str[<span class="number">50</span>];<span class="comment">//字符数组string，长度30</span></span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;请输入一个二进制数：\n&quot;</span>);</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>, str);<span class="comment">//输入二进制数</span></span><br><span class="line">	d = <span class="built_in">strlen</span>(str);</span><br><span class="line">	<span class="keyword">for</span> (i = <span class="number">0</span>; i &lt; d; i++) &#123; <span class="comment">//二进制转为十进制要从右到左用二进制的每个数去乘以2的相应次方求和</span></span><br><span class="line">		a = str[i] - <span class="number">48</span>;</span><br><span class="line">		b = <span class="built_in">pow</span>(<span class="number">2</span>, d - <span class="number">1</span> - i); <span class="comment">//2的次方</span></span><br><span class="line">		sum += a * b; <span class="comment">//十进制要从右到左用二进制的每个数去乘以2的相应次方相加</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, sum); <span class="comment">//输出十进制整数</span></span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h3 id="最大子树和"><a href="#最大子树和" class="headerlink" title="最大子树和"></a>最大子树和</h3><figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> MAX_SIZE 16005</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> MIN_VALUE -2147483647</span></span><br><span class="line"></span><br><span class="line"><span class="type">int</span> n, a[MAX_SIZE], f[MAX_SIZE], ans = MIN_VALUE;</span><br><span class="line"><span class="type">int</span>* E[MAX_SIZE];</span><br><span class="line"><span class="type">int</span> size[MAX_SIZE] = &#123;<span class="number">0</span>&#125;;</span><br><span class="line"></span><br><span class="line"><span class="type">void</span> <span class="title function_">dfs</span><span class="params">(<span class="type">int</span> u, <span class="type">int</span> fa)</span></span><br><span class="line">&#123;</span><br><span class="line">    f[u] = a[u]; <span class="comment">// 初始化 f 的值</span></span><br><span class="line">    <span class="type">int</span> i;</span><br><span class="line">    <span class="keyword">for</span> (i = <span class="number">0</span>; i &lt; size[u]; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="type">int</span> t = E[u][i];</span><br><span class="line">        <span class="keyword">if</span> (t != fa)</span><br><span class="line">        &#123;</span><br><span class="line">            dfs(t, u);</span><br><span class="line">            <span class="keyword">if</span> (f[t] &gt; <span class="number">0</span>)</span><br><span class="line">                f[u] += f[t]; <span class="comment">// 更新点权和</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> <span class="title function_">max</span><span class="params">(<span class="type">int</span> a, <span class="type">int</span> b)</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">return</span> (a &gt; b) ? a : b;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> <span class="title function_">main</span><span class="params">()</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;n);</span><br><span class="line">    <span class="type">int</span> i;</span><br><span class="line">    <span class="keyword">for</span> (i = <span class="number">1</span>; i &lt;= n; i++)</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;a[i]); <span class="comment">// 读入点权</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (i = <span class="number">1</span>; i &lt; n; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="type">int</span> u, v;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;u, &amp;v);</span><br><span class="line">        </span><br><span class="line">        <span class="comment">// 动态数组存储邻接表</span></span><br><span class="line">        E[u] = (<span class="type">int</span>*)<span class="built_in">realloc</span>(E[u], (size[u] + <span class="number">1</span>) * <span class="keyword">sizeof</span>(<span class="type">int</span>));</span><br><span class="line">        E[u][size[u]++] = v;</span><br><span class="line">        E[v] = (<span class="type">int</span>*)<span class="built_in">realloc</span>(E[v], (size[v] + <span class="number">1</span>) * <span class="keyword">sizeof</span>(<span class="type">int</span>));</span><br><span class="line">        E[v][size[v]++] = u;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    dfs(<span class="number">1</span>, <span class="number">0</span>);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (i = <span class="number">1</span>; i &lt;= n; i++)</span><br><span class="line">        ans = max(ans, f[i]); <span class="comment">// 找出最大点权和</span></span><br><span class="line"></span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;%d&quot;</span>, ans);</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h3 id="取不相邻的数"><a href="#取不相邻的数" class="headerlink" title="取不相邻的数"></a>取不相邻的数</h3><p><strong>一个 <em>N</em> × <em>M</em> 的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻 8 个格子中的一个即认为这两个数字相邻），求取出数字和最大是多少</strong></p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;bits/stdc++.h&gt;</span><span class="comment">//万能头文件 </span></span></span><br><span class="line">using namespace <span class="built_in">std</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> d[<span class="number">8</span>][<span class="number">2</span>]=&#123;<span class="number">1</span>,<span class="number">0</span>,<span class="number">-1</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">-1</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">-1</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">-1</span>,<span class="number">-1</span>,<span class="number">-1</span>&#125;;<span class="comment">//方向数组用来控制搜索时的方向 </span></span><br><span class="line"><span class="type">int</span> t,n,m,s[<span class="number">8</span>][<span class="number">8</span>],mark[<span class="number">8</span>][<span class="number">8</span>],ans,mx;</span><br><span class="line"><span class="type">void</span> <span class="title function_">dfs</span><span class="params">(<span class="type">int</span> x,<span class="type">int</span> y)</span>&#123;<span class="comment">//搜索函数，表示搜索点(x,y) </span></span><br><span class="line">	<span class="keyword">if</span>(y==m+<span class="number">1</span>)&#123;<span class="comment">//当y到边界时，搜索下一行 </span></span><br><span class="line">		dfs(x+<span class="number">1</span>,<span class="number">1</span>);</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>(x==n+<span class="number">1</span>)&#123;<span class="comment">//当x到边界时，搜索结束，刷新最大值 </span></span><br><span class="line">		mx=max(ans,mx);</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	dfs(x,y+<span class="number">1</span>);<span class="comment">// 不取此数的情况 </span></span><br><span class="line">	</span><br><span class="line">	<span class="keyword">if</span>(mark[x][y]==<span class="number">0</span>)&#123; <span class="comment">//取此数的情况（需保证此数周围没有取其他数，即mark[i][j]==0）</span></span><br><span class="line">		ans+=s[x][y];</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> fx=<span class="number">0</span>;fx&lt;<span class="number">8</span>;++fx)&#123; <span class="comment">//标记周围的数 </span></span><br><span class="line">			++mark[x+d[fx][<span class="number">0</span>]][y+d[fx][<span class="number">1</span>]];</span><br><span class="line">		&#125;</span><br><span class="line">		dfs(x,y+<span class="number">1</span>);</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> fx=<span class="number">0</span>;fx&lt;<span class="number">8</span>;++fx)&#123; <span class="comment">//回溯 </span></span><br><span class="line">			--mark[x+d[fx][<span class="number">0</span>]][y+d[fx][<span class="number">1</span>]];</span><br><span class="line">		&#125;</span><br><span class="line">		ans-=s[x][y];</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">&#125;</span><br><span class="line"><span class="type">int</span> <span class="title function_">main</span><span class="params">()</span>&#123;</span><br><span class="line">	<span class="built_in">cin</span>&gt;&gt;t; </span><br><span class="line">	<span class="keyword">while</span>(t--)&#123;</span><br><span class="line">		<span class="built_in">memset</span>(s,<span class="number">0</span>,<span class="keyword">sizeof</span>(s));</span><br><span class="line">		<span class="built_in">memset</span>(mark,<span class="number">0</span>,<span class="keyword">sizeof</span>(mark));<span class="comment">//在做每个数据前都要初始化数组 </span></span><br><span class="line">		<span class="built_in">cin</span>&gt;&gt;n&gt;&gt;m;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;++i)&#123;</span><br><span class="line">			<span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">1</span>;j&lt;=m;++j)&#123;</span><br><span class="line">				<span class="built_in">cin</span>&gt;&gt;s[i][j];</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		mx=<span class="number">0</span>;</span><br><span class="line">		dfs(<span class="number">1</span>,<span class="number">1</span>);<span class="comment">//从点(1,1)开始搜索 </span></span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>,mx);<span class="comment">//输出答案 </span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h2 id="流水线调度"><a href="#流水线调度" class="headerlink" title="流水线调度"></a>流水线调度</h2><p><img src="/.io//myblog\source_posts\补充板子\image-20230922155626744.png" alt="image-20230922155626744"></p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;math.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;string.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> ll;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 定义一个结构体TW，表示一个摊位的游戏所需时间。</span></span><br><span class="line"><span class="comment">// a代表路北摊位需要的时间，b代表路南摊位需要的时间。</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> &#123;</span></span><br><span class="line">    <span class="type">int</span> a;</span><br><span class="line">    <span class="type">int</span> b;</span><br><span class="line">&#125; TW;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 自定义一个max函数，返回两个整数中的较大值。</span></span><br><span class="line"><span class="type">int</span> <span class="title function_">max</span><span class="params">(<span class="type">int</span> a, <span class="type">int</span> b)</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> a &gt; b ? a : b;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 定义三个TW类型的数组。</span></span><br><span class="line"><span class="comment">// tw用于存储输入的n个摊位。</span></span><br><span class="line"><span class="comment">// tw1用于存储那些路北摊位游戏时间比路南摊位短的摊位。</span></span><br><span class="line"><span class="comment">// tw2用于存储其它摊位。</span></span><br><span class="line">TW tw[<span class="number">1005</span>], tw1[<span class="number">1005</span>], tw2[<span class="number">1005</span>];</span><br><span class="line"><span class="comment">// sum1用于记录在特定顺序下，到达每个摊位时的累计时间。</span></span><br><span class="line"><span class="comment">// sum2用于记录完成每个摊位游戏后的最短累计时间。</span></span><br><span class="line"><span class="type">int</span> sum1[<span class="number">1005</span>], sum2[<span class="number">1005</span>];</span><br><span class="line"></span><br><span class="line"><span class="comment">// 比较函数，用于将tw2中的摊位按照路南摊位所需时间从大到小排序。</span></span><br><span class="line"><span class="type">int</span> <span class="title function_">cmp</span><span class="params">(<span class="type">const</span> <span class="type">void</span> *a, <span class="type">const</span> <span class="type">void</span> *b)</span> &#123;</span><br><span class="line">    TW *p = (TW *)a;</span><br><span class="line">    TW *q = (TW *)b;</span><br><span class="line">    <span class="keyword">return</span> q-&gt;b - p-&gt;b;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 比较函数，用于将tw1中的摊位按照路北摊位所需时间从小到大排序。</span></span><br><span class="line"><span class="type">int</span> <span class="title function_">cmp2</span><span class="params">(<span class="type">const</span> <span class="type">void</span> *a, <span class="type">const</span> <span class="type">void</span> *b)</span> &#123;</span><br><span class="line">    TW *p = (TW *)a;</span><br><span class="line">    TW *q = (TW *)b;</span><br><span class="line">    <span class="keyword">return</span> p-&gt;a - q-&gt;a;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> <span class="title function_">main</span><span class="params">()</span> &#123;</span><br><span class="line">    <span class="type">int</span> n;</span><br><span class="line">    <span class="type">int</span> i, j = <span class="number">0</span>, k = <span class="number">0</span>;</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;n);  <span class="comment">// 读取摊位数量n</span></span><br><span class="line">    <span class="comment">// 读取每个摊位的路北游戏时间</span></span><br><span class="line">    <span class="keyword">for</span> (i = <span class="number">1</span>; i &lt;= n; i++) &#123;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;tw[i].a);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 读取每个摊位的路南游戏时间，并按照路北和路南的游戏时间将它们分类到tw1和tw2中</span></span><br><span class="line">    <span class="keyword">for</span> (i = <span class="number">1</span>; i &lt;= n; i++) &#123;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;tw[i].b);</span><br><span class="line">        <span class="keyword">if</span> (tw[i].a &lt; tw[i].b) &#123;</span><br><span class="line">            tw1[++j] = tw[i];</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            tw2[++k] = tw[i];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 对tw1和tw2进行排序</span></span><br><span class="line">    qsort(tw1 + <span class="number">1</span>, j, <span class="keyword">sizeof</span>(TW), cmp2);</span><br><span class="line">    qsort(tw2 + <span class="number">1</span>, k, <span class="keyword">sizeof</span>(TW), cmp);</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 初始化累计时间数组</span></span><br><span class="line">    sum1[<span class="number">0</span>] = <span class="number">0</span>, sum2[<span class="number">0</span>] = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 更新在访问tw1中的摊位后的累计时间</span></span><br><span class="line">    <span class="keyword">for</span> (i = <span class="number">1</span>; i &lt;= j; i++) &#123;</span><br><span class="line">        sum1[i] = sum1[i - <span class="number">1</span>] + tw1[i].a;</span><br><span class="line">        sum2[i] = max(sum1[i], sum2[i - <span class="number">1</span>]) + tw1[i].b;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">// 更新在访问tw2中的摊位后的累计时间</span></span><br><span class="line">    <span class="keyword">for</span> (i = <span class="number">1</span>; i &lt;= k; i++) &#123;</span><br><span class="line">        sum1[i + j] = sum1[i + j - <span class="number">1</span>] + tw2[i].a;</span><br><span class="line">        sum2[i + j] = max(sum1[i + j], sum2[i + j - <span class="number">1</span>]) + tw2[i].b;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 输出最短完成所有游戏的总时间</span></span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;%d&quot;</span>, sum2[n]);</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>


      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="https://mathieulin.gitee.io/2023/08/29/%E4%BF%9D%E7%A0%94%E9%9D%A2%E8%AF%95/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Mathieu Lin">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Mathieu's blog">
      <meta itemprop="description" content="这是一个记载了lzhow传奇的一生的博客">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | Mathieu's blog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2023/08/29/%E4%BF%9D%E7%A0%94%E9%9D%A2%E8%AF%95/" class="post-title-link" itemprop="url">保研面试</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2023-08-29 00:00:00" itemprop="dateCreated datePublished" datetime="2023-08-29T00:00:00+08:00">2023-08-29</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2023-09-23 19:48:08" itemprop="dateModified" datetime="2023-09-23T19:48:08+08:00">2023-09-23</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E4%BF%9D%E7%A0%94%E9%9D%A2%E8%AF%95%E5%A4%8D%E4%B9%A0/" itemprop="url" rel="index"><span itemprop="name">保研面试复习</span></a>
        </span>
    </span>

  
  
  <span class="post-meta-item">
    
    <span class="post-meta-item-icon">
      <i class="far fa-comment"></i>
    </span>
    <span class="post-meta-item-text">评论数：</span>
  
    <a title="waline" href="/2023/08/29/%E4%BF%9D%E7%A0%94%E9%9D%A2%E8%AF%95/#waline" itemprop="discussionUrl">
      <span class="post-comments-count waline-comment-count" data-path="/2023/08/29/%E4%BF%9D%E7%A0%94%E9%9D%A2%E8%AF%95/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <p>这是一个你奶奶都能懂的保研面试复习</p>
          <!--noindex-->
            <div class="post-button">
              <a class="btn" href="/2023/08/29/%E4%BF%9D%E7%A0%94%E9%9D%A2%E8%AF%95/">
                阅读全文 &raquo;
              </a>
            </div>
          <!--/noindex-->
        
      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="https://mathieulin.gitee.io/2023/08/29/%E6%9D%BF%E5%AD%90/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Mathieu Lin">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Mathieu's blog">
      <meta itemprop="description" content="这是一个记载了lzhow传奇的一生的博客">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | Mathieu's blog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2023/08/29/%E6%9D%BF%E5%AD%90/" class="post-title-link" itemprop="url">算法板子</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2023-08-29 00:00:00" itemprop="dateCreated datePublished" datetime="2023-08-29T00:00:00+08:00">2023-08-29</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2023-09-22 21:19:34" itemprop="dateModified" datetime="2023-09-22T21:19:34+08:00">2023-09-22</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">算法</span></a>
        </span>
    </span>

  
  
  <span class="post-meta-item">
    
    <span class="post-meta-item-icon">
      <i class="far fa-comment"></i>
    </span>
    <span class="post-meta-item-text">评论数：</span>
  
    <a title="waline" href="/2023/08/29/%E6%9D%BF%E5%AD%90/#waline" itemprop="discussionUrl">
      <span class="post-comments-count waline-comment-count" data-path="/2023/08/29/%E6%9D%BF%E5%AD%90/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <p>这是一个你奶奶都能懂的算法板子</p>
          <!--noindex-->
            <div class="post-button">
              <a class="btn" href="/2023/08/29/%E6%9D%BF%E5%AD%90/">
                阅读全文 &raquo;
              </a>
            </div>
          <!--/noindex-->
        
      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="https://mathieulin.gitee.io/2022/07/15/2022-07-15-%E6%B7%B1%E5%BA%A6%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Mathieu Lin">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Mathieu's blog">
      <meta itemprop="description" content="这是一个记载了lzhow传奇的一生的博客">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | Mathieu's blog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2022/07/15/2022-07-15-%E6%B7%B1%E5%BA%A6%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/" class="post-title-link" itemprop="url">深度学习笔记</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2022-07-15 00:00:00" itemprop="dateCreated datePublished" datetime="2022-07-15T00:00:00+08:00">2022-07-15</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2022-07-22 11:36:52" itemprop="dateModified" datetime="2022-07-22T11:36:52+08:00">2022-07-22</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E6%B7%B1%E5%BA%A6%E5%AD%A6%E4%B9%A0/" itemprop="url" rel="index"><span itemprop="name">深度学习</span></a>
        </span>
    </span>

  
  
  <span class="post-meta-item">
    
    <span class="post-meta-item-icon">
      <i class="far fa-comment"></i>
    </span>
    <span class="post-meta-item-text">评论数：</span>
  
    <a title="waline" href="/2022/07/15/2022-07-15-%E6%B7%B1%E5%BA%A6%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/#waline" itemprop="discussionUrl">
      <span class="post-comments-count waline-comment-count" data-path="/2022/07/15/2022-07-15-%E6%B7%B1%E5%BA%A6%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <p>这是一个你奶奶都能懂的前端项目部署博客</p>
          <!--noindex-->
            <div class="post-button">
              <a class="btn" href="/2022/07/15/2022-07-15-%E6%B7%B1%E5%BA%A6%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/">
                阅读全文 &raquo;
              </a>
            </div>
          <!--/noindex-->
        
      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="https://mathieulin.gitee.io/2022/06/26/Java%20%E5%A4%9A%E7%BA%BF%E7%A8%8B%E7%9F%A5%E8%AF%86%E6%80%BB%E7%BB%93/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Mathieu Lin">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Mathieu's blog">
      <meta itemprop="description" content="这是一个记载了lzhow传奇的一生的博客">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | Mathieu's blog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2022/06/26/Java%20%E5%A4%9A%E7%BA%BF%E7%A8%8B%E7%9F%A5%E8%AF%86%E6%80%BB%E7%BB%93/" class="post-title-link" itemprop="url">Java 多线程知识总结</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2022-06-26 22:59:31" itemprop="dateCreated datePublished" datetime="2022-06-26T22:59:31+08:00">2022-06-26</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2022-06-27 00:16:14" itemprop="dateModified" datetime="2022-06-27T00:16:14+08:00">2022-06-27</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/java/" itemprop="url" rel="index"><span itemprop="name">java</span></a>
        </span>
    </span>

  
  
  <span class="post-meta-item">
    
    <span class="post-meta-item-icon">
      <i class="far fa-comment"></i>
    </span>
    <span class="post-meta-item-text">评论数：</span>
  
    <a title="waline" href="/2022/06/26/Java%20%E5%A4%9A%E7%BA%BF%E7%A8%8B%E7%9F%A5%E8%AF%86%E6%80%BB%E7%BB%93/#waline" itemprop="discussionUrl">
      <span class="post-comments-count waline-comment-count" data-path="/2022/06/26/Java%20%E5%A4%9A%E7%BA%BF%E7%A8%8B%E7%9F%A5%E8%AF%86%E6%80%BB%E7%BB%93/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h1 id="Java-多线程知识总结"><a href="#Java-多线程知识总结" class="headerlink" title="Java 多线程知识总结"></a>Java 多线程知识总结</h1><h3 id="多线程概念引入"><a href="#多线程概念引入" class="headerlink" title="多线程概念引入"></a>多线程概念引入</h3><p>​		期末到了，要复习的科目很多，花叶对此感到很困惑。虽然花叶复习一门考试只需要半小时，但是要把眼前三十门课都给复习完，这还是要耗费花叶不少睡觉的时间的。</p>
<p>​		于是，花叶想，有没有一种方法，能够让自己可以复习得更快呢，毕竟刚买了好几款游戏。于是，花叶拔了自己的几根头发，然后变出了好几个花叶，一个花叶复习离散，一个花叶复习java，一个花叶复习数据库。。。。。。花叶发现，分成好几个人复习，效率贼高。看着看着离散，看困了又可以写写java大作业，写累了java又可以玩玩数据库，良性循环！</p>
<p><img src="https://vkceyugu.cdn.bspapp.com/VKCEYUGU-05d97c93-6101-4c53-8659-f5cf79396b93/3757dcb0-f418-450e-b279-d9724d82c856.png" alt="image-20220626213309918"></p>
<p>​		过了半小时，花叶便复习完了期末所有的内容，打开了它的steam。</p>
<p>​		在java中，我们的进程可以调用函数来执行特定的功能。但是，我们发现，进程在调用了函数之后，需要等待函数执行完毕了才能继续往下进行，即花叶需要在复习完离散之后，才可以开始复习java。那么，我们怎么才能像花叶一样，边复习离散，边复习java呢？这就引入了我们的线程的概念。</p>
<h3 id="线程的使用"><a href="#线程的使用" class="headerlink" title="线程的使用"></a>线程的使用</h3><p>​		我们在看奇奇怪怪的视频的时候，我们不仅能看到动态的图像，我们还能听到悦耳的声音，另外还伴随着准确无误的字幕，以及其他同道中人们精彩的弹幕讨论。那么，其实在视频播放器这个进程里，它是包含了图像，声音，字母，弹幕这些线程的。</p>
<p>​		又比如说，我们在与别人进行微信聊天的时候，也是有许许多多线程的，比如，一个线程在等待你的输入，一个线程在处理你的点击事件等。。。。。。</p>
<p>​		线程的实现其实并不是真正地能够同时实现多个任务，而是由于线程之间的切换非常迅速，因此让人觉得线程是能够同时执行的。比如说，花叶一边复习软工，一边复习数据库，但是一心不能二用，强如花叶也做不到，但是她之所以不是一般人，是因为她可以在两者中迅速切换，复习5ms数据库后又复习5ms的软工，然后又复习数据库。这样，在普通人的视角中，花叶仿佛同时完成了两件事情。</p>
<p><img src="https://vkceyugu.cdn.bspapp.com/VKCEYUGU-05d97c93-6101-4c53-8659-f5cf79396b93/d82eb568-01d1-4c43-b91a-62e2e256f291.png" alt="无标题"></p>
<p>​		这样可能不太容易理解，那么我们把格局打开，或者说我们从花叶（上帝）的视角来看普通人的生活，所谓天上一分钟，地上十年，勒布朗花叶两天连打了两场UBA，但是在上帝花叶看来，这中间其实就是几毫秒不到的时间，那么上帝花叶也就可以认为，勒布朗花叶同时打了两场比赛了。<img src="https://img1.baidu.com/it/u=3014455385,3131745615&fm=253&fmt=auto&app=138&f=PNG?w=647&h=451" alt="img"></p>
<h3 id="线程的创建"><a href="#线程的创建" class="headerlink" title="线程的创建"></a>线程的创建</h3><p>​		好了，我们在前面知道了线程是什么，那接下来我们就来看看线程应该怎么创建吧 ! 这里，我们来介绍线程的三种创建方式。</p>
<h4 id="继承Thread类"><a href="#继承Thread类" class="headerlink" title="继承Thread类"></a>继承Thread类</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Thread1</span> <span class="keyword">extends</span> <span class="title class_">Thread</span>&#123;</span><br><span class="line">	<span class="keyword">private</span> String name;</span><br><span class="line">    <span class="keyword">public</span> <span class="title function_">Thread1</span><span class="params">(String name)</span> &#123;</span><br><span class="line">       <span class="built_in">this</span>.name=name;</span><br><span class="line">    &#125;</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">run</span><span class="params">()</span> &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; <span class="number">5</span>; i++) &#123;</span><br><span class="line">            System.out.println(name + <span class="string">&quot;运行  :  &quot;</span> + i);</span><br><span class="line">            <span class="keyword">try</span> &#123;</span><br><span class="line">                sleep((<span class="type">int</span>) Math.random() * <span class="number">10</span>);</span><br><span class="line">            &#125; <span class="keyword">catch</span> (InterruptedException e) &#123;</span><br><span class="line">                e.printStackTrace();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">       </span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Main</span> &#123;</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">		Thread1 mTh1=<span class="keyword">new</span> <span class="title class_">Thread1</span>(<span class="string">&quot;A&quot;</span>);</span><br><span class="line">		Thread1 mTh2=<span class="keyword">new</span> <span class="title class_">Thread1</span>(<span class="string">&quot;B&quot;</span>);</span><br><span class="line">		mTh1.start();</span><br><span class="line">		mTh2.start();</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>运行结果如下：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">A运行  :  0</span><br><span class="line">B运行  :  0</span><br><span class="line">A运行  :  1</span><br><span class="line">B运行  :  1</span><br><span class="line">A运行  :  2</span><br><span class="line">B运行  :  2</span><br><span class="line">A运行  :  3</span><br><span class="line">B运行  :  3</span><br><span class="line">A运行  :  4</span><br><span class="line">B运行  :  4</span><br><span class="line"></span><br><span class="line">进程已结束,退出代码0</span><br></pre></td></tr></table></figure>

<p>​		在这个创建线程的方法中，我们创建了继承Thread类的Thread1类。我们在Main中通过new新建了一个线程，而通过线程的start()方法开启了线程（注意，这里只是将该线程变成了可运行态，具体什么时候运行取决于操作系统）。</p>
<p>​		而当该线程开始运行后，将调用run方法，当run方法运行完毕后，该线程结束。</p>
<p>​		花叶同学闲着无聊，于是多点了几次运行，发现了不太一样的运行结果：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">B运行  :  <span class="number">0</span></span><br><span class="line">A运行  :  <span class="number">0</span></span><br><span class="line">B运行  :  <span class="number">1</span></span><br><span class="line">B运行  :  <span class="number">2</span></span><br><span class="line">A运行  :  <span class="number">1</span></span><br><span class="line">B运行  :  <span class="number">3</span></span><br><span class="line">A运行  :  <span class="number">2</span></span><br><span class="line">B运行  :  <span class="number">4</span></span><br><span class="line">A运行  :  <span class="number">3</span></span><br><span class="line">A运行  :  <span class="number">4</span></span><br></pre></td></tr></table></figure>

<p>​		从程序运行的结果可以发现，多线程程序是乱序执行。因此，只有乱序执行的代码才有必要设计为多线程。<br>Thread.sleep()方法调用目的是不让当前线程独自霸占该进程所获取的CPU资源，以留出一定时间给其他线程执行的机会。<br>​		实际上所有的多线程代码执行顺序都是不确定的，每次执行的结果都是随机的。</p>
<p>​		这里的线程执行顺序问题涉及到了操作系统的线程调度问题啦！当然，这其实也很好理解，花叶在复习的时候，当然可以以一个比较固定的顺序来交替进行复习。但是花叶的性情多变，有时候复习完一门之后，还想再进一步地进行复习，而有时候又因为考的太高分了，一段时间内不想复习这一门，因此花叶的复习的顺序其实也是不确定的。</p>
<h4 id="实现Runnable接口"><a href="#实现Runnable接口" class="headerlink" title="实现Runnable接口"></a>实现Runnable接口</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Thread2</span> <span class="keyword">implements</span> <span class="title class_">Runnable</span>&#123;</span><br><span class="line">    <span class="keyword">private</span> String name;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="title function_">Thread2</span><span class="params">(String name)</span> &#123;</span><br><span class="line">        <span class="built_in">this</span>.name=name;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">run</span><span class="params">()</span> &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; <span class="number">5</span>; i++) &#123;</span><br><span class="line">            System.out.println(name + <span class="string">&quot;运行  :  &quot;</span> + i);</span><br><span class="line">            <span class="keyword">try</span> &#123;</span><br><span class="line">                Thread.sleep((<span class="type">int</span>) Math.random() * <span class="number">10</span>);</span><br><span class="line">            &#125; <span class="keyword">catch</span> (InterruptedException e) &#123;</span><br><span class="line">                e.printStackTrace();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Main2</span> &#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">        <span class="keyword">new</span> <span class="title class_">Thread</span>(<span class="keyword">new</span> <span class="title class_">Thread2</span>(<span class="string">&quot;C&quot;</span>)).start();</span><br><span class="line">        <span class="keyword">new</span> <span class="title class_">Thread</span>(<span class="keyword">new</span> <span class="title class_">Thread2</span>(<span class="string">&quot;D&quot;</span>)).start();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>执行结果如下：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line">A运行  :  0</span><br><span class="line">B运行  :  0</span><br><span class="line">A运行  :  1</span><br><span class="line">B运行  :  1</span><br><span class="line">A运行  :  2</span><br><span class="line">B运行  :  2</span><br><span class="line">A运行  :  3</span><br><span class="line">B运行  :  3</span><br><span class="line">A运行  :  4</span><br><span class="line">B运行  :  4</span><br><span class="line"></span><br><span class="line">进程已结束,退出代码0</span><br><span class="line"></span><br></pre></td></tr></table></figure>



<p>我们发现，其实执行结果和方法一没什么不一样的，也是随机的执行噢！</p>
<h4 id="实现Callable接口（了解）"><a href="#实现Callable接口（了解）" class="headerlink" title="实现Callable接口（了解）"></a>实现Callable接口（了解）</h4><h3 id="线程的状态转换"><a href="#线程的状态转换" class="headerlink" title="线程的状态转换"></a>线程的状态转换</h3><p>​		这里找了一张网上的图（画的太好了，而且自己画也不涨字数，就直接拿过来啦）</p>
<p><img src="https://vkceyugu.cdn.bspapp.com/VKCEYUGU-05d97c93-6101-4c53-8659-f5cf79396b93/f3c75a60-cadc-427e-b5d7-c57c62727417.png" alt="img"></p>
<p>​		我们看到，除了我们刚开始用到的start方法外，还有很多其他的方法。Thread.sleep()方法我们在上面的例子中也有用到过，而其他的这些步骤我们都将在下面来进行进一步地讲解。</p>
<p>​		花叶同学在复习的时候，由于一心不能二用，因此她同时其实还是只能复习一门课的内容。假如花叶正在火急火燎地复习的时候，手机响起了dingdong一声，她打开手机，发现她的舍友给她发了一道题目（题目名为java专题写作），花叶二话不说，将这项直接加进了自己的<del>have done list</del> to do list。但是她并没有马上去做，因为她知道五百页的离散PPT她需要接近一秒才能彻底看完！那么，她舍友给她发的作业线程此时便处于了等待态。待花叶学累了离散（可能就几毫秒吧），花叶便将离散这一线程放入了等待队列中，然后从队列中挑了一个作业来继续运行 。舍友好不容易等到花叶开始帮他做java专题写作（不要好奇为什么她的舍友是他），花叶却发现他粗心的舍友居然没有告诉她要写些什么。没办法，花叶只能缓缓地向她的舍友打出了一个问号。舍友可能去打球了，花叶不能这么等着舍友，因为一分钟的时间足够花叶复习几十门课了，于是花叶将可怜的舍友的作业丢到了阻塞队列中。舍友本以为花叶能在十毫秒内帮他做完这个作业，开开心心地关掉了游戏，打开了微信，只看到花叶缓缓地打出了一个“？”</p>
<p>​		于是，舍友只能爬上了花叶的床，对着她的耳朵大声疾呼：“我爱多线程！”话音未落，这个线程便从阻塞态变成了等候态。舍友刚从床上爬了下来，花叶便已经将这五千字长文发给了他。</p>
<h3 id="线程的多个状态以及方法"><a href="#线程的多个状态以及方法" class="headerlink" title="线程的多个状态以及方法"></a>线程的多个状态以及方法</h3><h4 id="停止线程"><a href="#停止线程" class="headerlink" title="停止线程"></a>停止线程</h4><p>​		花叶已经完成了数据库的学习，那么怎么才能将数据库从花叶的等待库中停止呢？花叶当然可以在复习完后发出命令，停止这门课的复习，但是这多多少少增加了花叶的工作量，不太方便啊！于是花叶想到，当每门课的ppt看完了最后一页，那么就标志着这门课复习完毕了，就不需要再进行复习了（满分！）</p>
<p>​		在java中，我们可以在线程中设置标志位，当达到条件时，我们将标志位置0，然后直接在线程中执行stop方法，便可以使该线程停止咯！</p>
<h4 id="线程休眠"><a href="#线程休眠" class="headerlink" title="线程休眠"></a>线程休眠</h4><p>​		sleep方法我们在前面已经见过了很多次了，其实的话就是相当于延时操作。但是对象具有锁，使用sleep方法并不会释放锁，因此当其他进程尝试申请锁时会被拒绝。</p>
<h4 id="线程礼让"><a href="#线程礼让" class="headerlink" title="线程礼让"></a>线程礼让</h4><p>​		yield方法，可以让当前执行的线程暂停，但是不阻塞。当前线程进入到就绪队列，由CPU进行再次调度。</p>
<p>​		花叶考试的时候总会礼让一下同学们，她会让其他同学先做题，然后她再做。有时候，其它同学会比她更快地做完一道题，但是其他时候，她都能比其他同学先做完。于是，花叶经常说：“我先睡会儿又如何？”</p>
<h4 id="线程合并"><a href="#线程合并" class="headerlink" title="线程合并"></a>线程合并</h4><p>​		join方法，阻塞其他线程，当该线程执行完毕后，其他线程才能继续执行。</p>
<p>​		花叶想打游戏了，因此她会放下其他所有复习的任务，先打游戏，只有当花叶不想打游戏了，她才会继续复习。</p>
<h3 id="多个线程并发"><a href="#多个线程并发" class="headerlink" title="多个线程并发"></a>多个线程并发</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line">class TestThread3 implements Runnable&#123;</span><br><span class="line">    private int ticketNums = 10;</span><br><span class="line"></span><br><span class="line">    @Override</span><br><span class="line">    public void run()&#123;</span><br><span class="line">        while(true)&#123;</span><br><span class="line">            if(ticketNums&lt;=0)&#123;</span><br><span class="line">                break;</span><br><span class="line">            &#125;</span><br><span class="line">            try &#123;</span><br><span class="line">                Thread.sleep(200);</span><br><span class="line">            &#125; catch (InterruptedException e) &#123;</span><br><span class="line">                e.printStackTrace();</span><br><span class="line">            &#125;</span><br><span class="line">            System.out.println(Thread.currentThread().getName()+&quot;--&gt;拿到了&quot;+ticketNums--+&quot;票&quot;);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">public class Main3 &#123;</span><br><span class="line">    public static void main(String[] args)&#123;</span><br><span class="line">        TestThread3 ticket = new TestThread3();</span><br><span class="line">        new Thread(ticket, &quot;小明&quot;).start();</span><br><span class="line">        new Thread(ticket, &quot;小红&quot;).start();</span><br><span class="line">        new Thread(ticket, &quot;小蓝&quot;).start();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>得到输出结果如下：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">小红--&gt;拿到了10票</span><br><span class="line">小蓝--&gt;拿到了9票</span><br><span class="line">小明--&gt;拿到了8票</span><br><span class="line">小蓝--&gt;拿到了7票</span><br><span class="line">小红--&gt;拿到了5票</span><br><span class="line">小明--&gt;拿到了6票</span><br><span class="line">小明--&gt;拿到了4票</span><br><span class="line">小蓝--&gt;拿到了3票</span><br><span class="line">小红--&gt;拿到了4票</span><br><span class="line">小明--&gt;拿到了2票</span><br><span class="line">小蓝--&gt;拿到了2票</span><br><span class="line">小红--&gt;拿到了2票</span><br><span class="line">小明--&gt;拿到了1票</span><br><span class="line">小蓝--&gt;拿到了-1票</span><br><span class="line">小红--&gt;拿到了0票</span><br></pre></td></tr></table></figure>

<p>​		花叶惊喜地发现，大家一共拿了超过了10张票，甚至出现了负票的怪状。花叶发现，假如这样的话，她有一千块，每次拿一百块，她可以拿到1600块，运气好时甚至可以更多！！！于是，她让室友去银行试了试，银行工作人员直接把室友给轰了出来。</p>
<p>​		线程在并发执行时，容易出现数据紊乱的情况，即多个线程同时对一个数据进行读写操作，会出现一些奇怪的问题。那么，银行是怎么防止这个情况发生的呢？</p>
<p>​		当用户取钱的时候，银行会给这个账号加上保护锁，即这个账号此时没法在其他地方进行取款的操作。只有当用户取完款后，银行再把这个锁给取消，其他地方才能进行取款操作。而线程其实也是一样，当线程要对数据进行读写的时候，我们需要给数据加上一个锁（写锁或读锁）。</p>
<p>​		解决方法也很简单，其实给run添加锁就可以了。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.util.concurrent.locks.Lock;</span><br><span class="line"><span class="keyword">import</span> java.util.concurrent.locks.ReentrantLock;</span><br><span class="line"></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">TestThread3</span> <span class="keyword">implements</span> <span class="title class_">Runnable</span>&#123;</span><br><span class="line">    <span class="keyword">private</span> <span class="type">int</span> <span class="variable">ticketNums</span> <span class="operator">=</span> <span class="number">10</span>;</span><br><span class="line"></span><br><span class="line">    <span class="type">Lock</span> <span class="variable">lock</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">ReentrantLock</span>();</span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">run</span><span class="params">()</span> &#123;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span> (<span class="literal">true</span>) &#123;</span><br><span class="line"></span><br><span class="line">            <span class="keyword">try</span> &#123;</span><br><span class="line">                lock.lock();</span><br><span class="line">                <span class="keyword">if</span> (ticketNums &lt;= <span class="number">0</span>) &#123;</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                Thread.sleep(<span class="number">200</span>);</span><br><span class="line">                </span><br><span class="line">            &#125; <span class="keyword">catch</span> (InterruptedException e) &#123;</span><br><span class="line">                e.printStackTrace();</span><br><span class="line">            &#125;<span class="keyword">finally</span> &#123;</span><br><span class="line">                lock.unlock();</span><br><span class="line">            &#125;</span><br><span class="line">            System.out.println(Thread.currentThread().getName() + <span class="string">&quot;--&gt;拿到了&quot;</span> + ticketNums-- + <span class="string">&quot;票&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Main3</span> &#123;</span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span>&#123;</span><br><span class="line">        <span class="type">TestThread3</span> <span class="variable">ticket</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">TestThread3</span>();</span><br><span class="line">        <span class="keyword">new</span> <span class="title class_">Thread</span>(ticket, <span class="string">&quot;小明&quot;</span>).start();</span><br><span class="line">        <span class="keyword">new</span> <span class="title class_">Thread</span>(ticket, <span class="string">&quot;小红&quot;</span>).start();</span><br><span class="line">        <span class="keyword">new</span> <span class="title class_">Thread</span>(ticket, <span class="string">&quot;小蓝&quot;</span>).start();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p>结果如下：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line">小明--&gt;拿到了10票</span><br><span class="line">小红--&gt;拿到了9票</span><br><span class="line">小蓝--&gt;拿到了8票</span><br><span class="line">小明--&gt;拿到了7票</span><br><span class="line">小红--&gt;拿到了6票</span><br><span class="line">小蓝--&gt;拿到了5票</span><br><span class="line">小明--&gt;拿到了4票</span><br><span class="line">小红--&gt;拿到了3票</span><br><span class="line">小蓝--&gt;拿到了2票</span><br><span class="line">小明--&gt;拿到了1票</span><br><span class="line"></span><br><span class="line">进程已结束,退出代码0</span><br><span class="line"></span><br><span class="line"></span><br></pre></td></tr></table></figure>



<p>​		当然，当我们给这个属性加锁之后，一个属性还好，假如有多个属性的话，当一个线程等待另一个线程的锁释放，而另一个线程又在等待这个线程的锁释放的时候，就会出现死锁的问题。而死锁的解决我们在操作系统以及数据库的学习中已经学习了不少了，这里就不再加以总结了。</p>
<p>​		PS：花叶的舍友在此感谢花叶的友情出演，虽然花叶可能自己都不知道自己出演了。</p>

      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="https://mathieulin.gitee.io/2022/06/10/2022-06-10-Ubuntu%E9%85%8D%E7%BD%AE/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Mathieu Lin">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Mathieu's blog">
      <meta itemprop="description" content="这是一个记载了lzhow传奇的一生的博客">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | Mathieu's blog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2022/06/10/2022-06-10-Ubuntu%E9%85%8D%E7%BD%AE/" class="post-title-link" itemprop="url">Ubuntu配置</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>
      

      <time title="创建时间：2022-06-10 13:14:37 / 修改时间：19:54:28" itemprop="dateCreated datePublished" datetime="2022-06-10T13:14:37+08:00">2022-06-10</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E8%99%9A%E6%8B%9F%E6%9C%BA/" itemprop="url" rel="index"><span itemprop="name">虚拟机</span></a>
        </span>
    </span>

  
  
  <span class="post-meta-item">
    
    <span class="post-meta-item-icon">
      <i class="far fa-comment"></i>
    </span>
    <span class="post-meta-item-text">评论数：</span>
  
    <a title="waline" href="/2022/06/10/2022-06-10-Ubuntu%E9%85%8D%E7%BD%AE/#waline" itemprop="discussionUrl">
      <span class="post-comments-count waline-comment-count" data-path="/2022/06/10/2022-06-10-Ubuntu%E9%85%8D%E7%BD%AE/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h1 id="1-vue项目的安装"><a href="#1-vue项目的安装" class="headerlink" title="1. vue项目的安装"></a>1. vue项目的安装</h1>
      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="https://mathieulin.gitee.io/2022/06/02/hello-world/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Mathieu Lin">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Mathieu's blog">
      <meta itemprop="description" content="这是一个记载了lzhow传奇的一生的博客">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | Mathieu's blog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2022/06/02/hello-world/" class="post-title-link" itemprop="url">Hello World</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>
      

      <time title="创建时间：2022-06-02 13:14:37 / 修改时间：16:44:29" itemprop="dateCreated datePublished" datetime="2022-06-02T13:14:37+08:00">2022-06-02</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/java/" itemprop="url" rel="index"><span itemprop="name">java</span></a>
        </span>
    </span>

  
  
  <span class="post-meta-item">
    
    <span class="post-meta-item-icon">
      <i class="far fa-comment"></i>
    </span>
    <span class="post-meta-item-text">评论数：</span>
  
    <a title="waline" href="/2022/06/02/hello-world/#waline" itemprop="discussionUrl">
      <span class="post-comments-count waline-comment-count" data-path="/2022/06/02/hello-world/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <p>Welcome to <a target="_blank" rel="noopener" href="https://hexo.io/">Hexo</a>! This is your very first post. Check <a target="_blank" rel="noopener" href="https://hexo.io/docs/">documentation</a> for more info. If you get any problems when using Hexo, you can find the answer in <a target="_blank" rel="noopener" href="https://hexo.io/docs/troubleshooting.html">troubleshooting</a> or you can ask me on <a target="_blank" rel="noopener" href="https://github.com/hexojs/hexo/issues">GitHub</a>.</p>
<h2 id="Quick-Start"><a href="#Quick-Start" class="headerlink" title="Quick Start"></a>Quick Start</h2><h3 id="Create-a-new-post"><a href="#Create-a-new-post" class="headerlink" title="Create a new post"></a>Create a new post</h3><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">$ hexo new <span class="string">&quot;My New Post&quot;</span></span><br></pre></td></tr></table></figure>

<p>More info: <a target="_blank" rel="noopener" href="https://hexo.io/docs/writing.html">Writing</a></p>
<h3 id="Run-server"><a href="#Run-server" class="headerlink" title="Run server"></a>Run server</h3><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">$ hexo server</span><br></pre></td></tr></table></figure>

<p>More info: <a target="_blank" rel="noopener" href="https://hexo.io/docs/server.html">Server</a></p>
<h3 id="Generate-static-files"><a href="#Generate-static-files" class="headerlink" title="Generate static files"></a>Generate static files</h3><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">$ hexo generate</span><br></pre></td></tr></table></figure>

<p>More info: <a target="_blank" rel="noopener" href="https://hexo.io/docs/generating.html">Generating</a></p>
<h3 id="Deploy-to-remote-sites"><a href="#Deploy-to-remote-sites" class="headerlink" title="Deploy to remote sites"></a>Deploy to remote sites</h3><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">$ hexo deploy</span><br></pre></td></tr></table></figure>

<p>More info: <a target="_blank" rel="noopener" href="https://hexo.io/docs/one-command-deployment.html">Deployment</a></p>

      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="https://mathieulin.gitee.io/2022/06/02/%E5%89%8D%E5%90%8E%E7%AB%AF%E4%BA%A4%E4%BA%92/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Mathieu Lin">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Mathieu's blog">
      <meta itemprop="description" content="这是一个记载了lzhow传奇的一生的博客">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | Mathieu's blog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2022/06/02/%E5%89%8D%E5%90%8E%E7%AB%AF%E4%BA%A4%E4%BA%92/" class="post-title-link" itemprop="url">前后端交互</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>
      

      <time title="创建时间：2022-06-02 13:14:37 / 修改时间：20:05:27" itemprop="dateCreated datePublished" datetime="2022-06-02T13:14:37+08:00">2022-06-02</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/java/" itemprop="url" rel="index"><span itemprop="name">java</span></a>
        </span>
    </span>

  
  
  <span class="post-meta-item">
    
    <span class="post-meta-item-icon">
      <i class="far fa-comment"></i>
    </span>
    <span class="post-meta-item-text">评论数：</span>
  
    <a title="waline" href="/2022/06/02/%E5%89%8D%E5%90%8E%E7%AB%AF%E4%BA%A4%E4%BA%92/#waline" itemprop="discussionUrl">
      <span class="post-comments-count waline-comment-count" data-path="/2022/06/02/%E5%89%8D%E5%90%8E%E7%AB%AF%E4%BA%A4%E4%BA%92/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h1 id="1-vue项目的安装"><a href="#1-vue项目的安装" class="headerlink" title="1. vue项目的安装"></a>1. vue项目的安装</h1><h2 id="1-1-依赖环境"><a href="#1-1-依赖环境" class="headerlink" title="1.1 依赖环境"></a>1.1 依赖环境</h2><p>Vue CLI 4.x 需要 Node.js v8.9 或更高版本 (推荐 v10 以上)。</p>
<h2 id="1-2-安装指令"><a href="#1-2-安装指令" class="headerlink" title="1.2 安装指令"></a>1.2 安装指令</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">npm install -g @vue/cli</span><br></pre></td></tr></table></figure>

<h2 id="1-3-检查指令"><a href="#1-3-检查指令" class="headerlink" title="1.3 检查指令"></a>1.3 检查指令</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">vue --version</span><br></pre></td></tr></table></figure>

<p><img src="/.io//vue_version.png"></p>
<h2 id="1-4-创建项目"><a href="#1-4-创建项目" class="headerlink" title="1.4 创建项目"></a>1.4 创建项目</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">vue create frontend</span><br></pre></td></tr></table></figure>

<h2 id="1-5-运行项目"><a href="#1-5-运行项目" class="headerlink" title="1.5 运行项目"></a>1.5 运行项目</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">npm run serve</span><br></pre></td></tr></table></figure>

<p>运行命令后可在http:localhost:8000&#x2F;中看到初始化项目</p>
<h2 id="1-6-安装axios"><a href="#1-6-安装axios" class="headerlink" title="1.6 安装axios"></a>1.6 安装axios</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">npm install axios</span><br></pre></td></tr></table></figure>

<h2 id="1-7-发送请求"><a href="#1-7-发送请求" class="headerlink" title="1.7 发送请求"></a>1.7 发送请求</h2><p>比如给按钮绑定了response方法，则在该vue的export default下</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> axios <span class="keyword">from</span> <span class="string">&#x27;axios&#x27;</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">export</span> <span class="keyword">default</span> &#123;</span><br><span class="line">    <span class="attr">name</span>: <span class="string">&#x27;App&#x27;</span>,</span><br><span class="line">    <span class="attr">components</span>: &#123;</span><br><span class="line">      </span><br><span class="line">    &#125;,</span><br><span class="line">    <span class="attr">methods</span>: &#123;</span><br><span class="line">      	<span class="title function_">response</span>(<span class="params"></span>)&#123;</span><br><span class="line">    		<span class="title class_">Axios</span>.<span class="title function_">get</span>(<span class="string">&quot;http://localhost:3000/product&quot;</span>).<span class="title function_">then</span>(<span class="keyword">function</span>(<span class="params">response</span>)&#123;</span><br><span class="line">          		<span class="variable language_">console</span>.<span class="title function_">log</span>(response);</span><br><span class="line">        	&#125;)	</span><br><span class="line">        &#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h1 id="2-Express项目"><a href="#2-Express项目" class="headerlink" title="2.Express项目"></a>2.Express项目</h1><h2 id="2-1-安装Express"><a href="#2-1-安装Express" class="headerlink" title="2.1 安装Express"></a>2.1 安装Express</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">npm install express --save</span><br></pre></td></tr></table></figure>

<h2 id="2-2-安装express应用程序生成器"><a href="#2-2-安装express应用程序生成器" class="headerlink" title="2.2 安装express应用程序生成器"></a>2.2 安装express应用程序生成器</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">npm install -g express-generator</span><br></pre></td></tr></table></figure>

<h2 id="2-3-创建名为backend的Express应用"><a href="#2-3-创建名为backend的Express应用" class="headerlink" title="2.3 创建名为backend的Express应用"></a>2.3 创建名为backend的Express应用</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">express --view=pug backend</span><br></pre></td></tr></table></figure>

<h2 id="2-4-按照提示进行操作"><a href="#2-4-按照提示进行操作" class="headerlink" title="2.4 按照提示进行操作"></a>2.4 按照提示进行操作</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">cd backend</span><br><span class="line">npm install</span><br><span class="line">SET DEBUG=backend:*</span><br><span class="line">npm start(建议在vscode中进行这一步)</span><br></pre></td></tr></table></figure>



<h2 id="2-5-提供接口请求"><a href="#2-5-提供接口请求" class="headerlink" title="2.5 提供接口请求"></a>2.5 提供接口请求</h2><h3 id="routes下新建product-js"><a href="#routes下新建product-js" class="headerlink" title="routes下新建product.js"></a>routes下新建product.js</h3><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> express = <span class="built_in">require</span>(<span class="string">&#x27;express&#x27;</span>);</span><br><span class="line"><span class="keyword">var</span> router = express.<span class="title class_">Router</span>();</span><br><span class="line"><span class="comment">/* GET home page. */</span></span><br><span class="line">router.<span class="title function_">get</span>(<span class="string">&#x27;/&#x27;</span>, <span class="keyword">function</span>(<span class="params">req, res, next</span>) &#123;</span><br><span class="line">	<span class="keyword">var</span> data=&#123;</span><br><span class="line">		<span class="attr">code</span>:<span class="number">0</span>,</span><br><span class="line">		<span class="attr">data</span>:&#123;<span class="attr">name</span>:<span class="string">&#x27;aaa&#x27;</span>,<span class="attr">pwd</span>:<span class="string">&#x27;123&#x27;</span>&#125;,</span><br><span class="line">		<span class="attr">isSuccess</span>:<span class="literal">true</span>,</span><br><span class="line">		<span class="attr">msg</span>:<span class="string">&quot;请求成功&quot;</span></span><br><span class="line">	&#125;</span><br><span class="line">	res.<span class="title function_">json</span>(data);</span><br><span class="line">&#125;);</span><br><span class="line"> </span><br><span class="line"><span class="variable language_">module</span>.<span class="property">exports</span> = router;</span><br><span class="line"></span><br></pre></td></tr></table></figure>

<h3 id="app-js设置跨域访问"><a href="#app-js设置跨域访问" class="headerlink" title="app.js设置跨域访问"></a>app.js设置跨域访问</h3><p>示例如下：</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> createError = <span class="built_in">require</span>(<span class="string">&#x27;http-errors&#x27;</span>);</span><br><span class="line"><span class="keyword">var</span> express = <span class="built_in">require</span>(<span class="string">&#x27;express&#x27;</span>);</span><br><span class="line"><span class="keyword">var</span> path = <span class="built_in">require</span>(<span class="string">&#x27;path&#x27;</span>);</span><br><span class="line"><span class="keyword">var</span> cookieParser = <span class="built_in">require</span>(<span class="string">&#x27;cookie-parser&#x27;</span>);</span><br><span class="line"><span class="keyword">var</span> logger = <span class="built_in">require</span>(<span class="string">&#x27;morgan&#x27;</span>);</span><br><span class="line"></span><br><span class="line"><span class="keyword">var</span> indexRouter = <span class="built_in">require</span>(<span class="string">&#x27;./routes/index&#x27;</span>);</span><br><span class="line"><span class="keyword">var</span> usersRouter = <span class="built_in">require</span>(<span class="string">&#x27;./routes/users&#x27;</span>);</span><br><span class="line"><span class="keyword">var</span> productRouter = <span class="built_in">require</span>(<span class="string">&#x27;./routes/product&#x27;</span>);</span><br><span class="line"></span><br><span class="line"><span class="keyword">var</span> app = <span class="title function_">express</span>();</span><br><span class="line"></span><br><span class="line"><span class="comment">// view engine setup</span></span><br><span class="line">app.<span class="title function_">set</span>(<span class="string">&#x27;views&#x27;</span>, path.<span class="title function_">join</span>(__dirname, <span class="string">&#x27;views&#x27;</span>));</span><br><span class="line">app.<span class="title function_">set</span>(<span class="string">&#x27;view engine&#x27;</span>, <span class="string">&#x27;jade&#x27;</span>);</span><br><span class="line"></span><br><span class="line">app.<span class="title function_">use</span>(<span class="title function_">logger</span>(<span class="string">&#x27;dev&#x27;</span>));</span><br><span class="line">app.<span class="title function_">use</span>(express.<span class="title function_">json</span>());</span><br><span class="line">app.<span class="title function_">use</span>(express.<span class="title function_">urlencoded</span>(&#123; <span class="attr">extended</span>: <span class="literal">false</span> &#125;));</span><br><span class="line">app.<span class="title function_">use</span>(<span class="title function_">cookieParser</span>());</span><br><span class="line">app.<span class="title function_">use</span>(express.<span class="title function_">static</span>(path.<span class="title function_">join</span>(__dirname, <span class="string">&#x27;public&#x27;</span>)));</span><br><span class="line"></span><br><span class="line"><span class="comment">//设置跨域访问</span></span><br><span class="line">app.<span class="title function_">all</span>(<span class="string">&#x27;*&#x27;</span>, <span class="keyword">function</span> (<span class="params">req, res, next</span>) &#123;</span><br><span class="line">  res.<span class="title function_">header</span>(<span class="string">&quot;Access-Control-Allow-Origin&quot;</span>, <span class="string">&quot;*&quot;</span>);</span><br><span class="line">  res.<span class="title function_">header</span>(<span class="string">&quot;Access-Control-Allow-Headers&quot;</span>, <span class="string">&quot;X-Requested-With&quot;</span>);</span><br><span class="line">  res.<span class="title function_">header</span>(<span class="string">&quot;Access-Control-Allow-Methods&quot;</span>, <span class="string">&quot;PUT,POST,GET,DELETE,OPTIONS&quot;</span>);</span><br><span class="line">  res.<span class="title function_">header</span>(<span class="string">&quot;X-Powered-By&quot;</span>, <span class="string">&#x27; 3.2.1&#x27;</span>)</span><br><span class="line">  res.<span class="title function_">header</span>(<span class="string">&quot;Content-Type&quot;</span>, <span class="string">&quot;application/json;charset=utf-8&quot;</span>);</span><br><span class="line">  <span class="title function_">next</span>();</span><br><span class="line">&#125;);</span><br><span class="line"></span><br><span class="line">app.<span class="title function_">use</span>(<span class="string">&#x27;/&#x27;</span>, indexRouter);</span><br><span class="line">app.<span class="title function_">use</span>(<span class="string">&#x27;/users&#x27;</span>, usersRouter);</span><br><span class="line">app.<span class="title function_">use</span>(<span class="string">&#x27;/product&#x27;</span>, productRouter);</span><br><span class="line"></span><br><span class="line"><span class="comment">// catch 404 and forward to error handler</span></span><br><span class="line">app.<span class="title function_">use</span>(<span class="keyword">function</span> (<span class="params">req, res, next</span>) &#123;</span><br><span class="line">  <span class="title function_">next</span>(<span class="title function_">createError</span>(<span class="number">404</span>));</span><br><span class="line">&#125;);</span><br><span class="line"></span><br><span class="line"><span class="comment">// error handler</span></span><br><span class="line">app.<span class="title function_">use</span>(<span class="keyword">function</span> (<span class="params">err, req, res, next</span>) &#123;</span><br><span class="line">  <span class="comment">// set locals, only providing error in development</span></span><br><span class="line">  res.<span class="property">locals</span>.<span class="property">message</span> = err.<span class="property">message</span>;</span><br><span class="line">  res.<span class="property">locals</span>.<span class="property">error</span> = req.<span class="property">app</span>.<span class="title function_">get</span>(<span class="string">&#x27;env&#x27;</span>) === <span class="string">&#x27;development&#x27;</span> ? err : &#123;&#125;;</span><br><span class="line"></span><br><span class="line">  <span class="comment">// render the error page</span></span><br><span class="line">  res.<span class="title function_">status</span>(err.<span class="property">status</span> || <span class="number">500</span>);</span><br><span class="line">  res.<span class="title function_">render</span>(<span class="string">&#x27;error&#x27;</span>);</span><br><span class="line">&#125;);</span><br><span class="line"></span><br><span class="line"><span class="variable language_">module</span>.<span class="property">exports</span> = app;</span><br><span class="line"></span><br><span class="line"></span><br></pre></td></tr></table></figure>

<h4 id="若需提供其他接口，则只需在route下新建一个-example-js，并且在app-js中添加下面两句"><a href="#若需提供其他接口，则只需在route下新建一个-example-js，并且在app-js中添加下面两句" class="headerlink" title="若需提供其他接口，则只需在route下新建一个(example.)js，并且在app.js中添加下面两句"></a>若需提供其他接口，则只需在route下新建一个(example.)js，并且在app.js中添加下面两句</h4><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> exampleRouter = <span class="built_in">require</span>(<span class="string">&#x27;./routes/example&#x27;</span>);</span><br><span class="line">app.<span class="title function_">use</span>(<span class="string">&#x27;/example&#x27;</span>, exampleRouter);</span><br></pre></td></tr></table></figure>



<h2 id="2-6-运行后端"><a href="#2-6-运行后端" class="headerlink" title="2.6 运行后端"></a>2.6 运行后端</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">npm start</span><br></pre></td></tr></table></figure>





<h1 id="3-交互"><a href="#3-交互" class="headerlink" title="3. 交互"></a>3. 交互</h1><p>打开前端网站，点击按钮，然后就可以在控制台上看到请求值了</p>

      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="https://mathieulin.gitee.io/2022/06/01/%E5%90%8E%E7%AB%AF%E9%83%A8%E7%BD%B2/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Mathieu Lin">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Mathieu's blog">
      <meta itemprop="description" content="这是一个记载了lzhow传奇的一生的博客">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | Mathieu's blog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2022/06/01/%E5%90%8E%E7%AB%AF%E9%83%A8%E7%BD%B2/" class="post-title-link" itemprop="url">后端项目傻逼式部署</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2022-06-01 00:00:00" itemprop="dateCreated datePublished" datetime="2022-06-01T00:00:00+08:00">2022-06-01</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2022-06-06 17:12:48" itemprop="dateModified" datetime="2022-06-06T17:12:48+08:00">2022-06-06</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E5%90%8E%E7%AB%AF/" itemprop="url" rel="index"><span itemprop="name">后端</span></a>
        </span>
    </span>

  
  
  <span class="post-meta-item">
    
    <span class="post-meta-item-icon">
      <i class="far fa-comment"></i>
    </span>
    <span class="post-meta-item-text">评论数：</span>
  
    <a title="waline" href="/2022/06/01/%E5%90%8E%E7%AB%AF%E9%83%A8%E7%BD%B2/#waline" itemprop="discussionUrl">
      <span class="post-comments-count waline-comment-count" data-path="/2022/06/01/%E5%90%8E%E7%AB%AF%E9%83%A8%E7%BD%B2/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <p>这是一个你奶奶都能懂的后端项目部署博客</p>
          <!--noindex-->
            <div class="post-button">
              <a class="btn" href="/2022/06/01/%E5%90%8E%E7%AB%AF%E9%83%A8%E7%BD%B2/">
                阅读全文 &raquo;
              </a>
            </div>
          <!--/noindex-->
        
      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




  <nav class="pagination">
    <span class="page-number current">1</span><a class="page-number" href="/page/2/">2</a><a class="extend next" rel="next" href="/page/2/"><i class="fa fa-angle-right" aria-label="下一页"></i></a>
  </nav>

</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">


<div class="copyright">
  &copy; 
  <span itemprop="copyrightYear">2023</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Mathieu Lin</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
  </div><script color="0,0,255" opacity="0.5" zIndex="-1" count="99" src="https://cdnjs.sourcegcdn.com//ajax/libs/canvas-nest.js/1.0.1/canvas-nest.js"></script>

    </div>
  </footer>

  
  <script src="https://cdnjs.cloudflare.com/ajax/libs/animejs/3.2.1/anime.min.js" integrity="sha256-XL2inqUJaslATFnHdJOi9GfQ60on8Wx1C2H8DYiN1xY=" crossorigin="anonymous"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/next-theme-pjax/0.5.0/pjax.min.js" integrity="sha256-3NkoLDrmHLTYj7csHIZSr0MHAFTXth7Ua/DDt4MRUAg=" crossorigin="anonymous"></script>
<script src="/js/comments.js"></script><script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/next-boot.js"></script><script src="/js/pjax.js"></script>

  
<script src="https://cdnjs.cloudflare.com/ajax/libs/hexo-generator-searchdb/1.4.0/search.js" integrity="sha256-vXZMYLEqsROAXkEw93GGIvaB2ab+QW6w3+1ahD9nXXA=" crossorigin="anonymous"></script>
<script src="/js/third-party/search/local-search.js"></script>





  




<script class="next-config" data-name="waline" type="application/json">{"lang":"zh-CN","enable":true,"serverURL":"https://blog-commeny-mh5e4d5jo-mathieulin.vercel.app","cssUrl":"https://unpkg.com/@waline/client@v2/dist/waline.css","commentCount":true,"pageview":false,"el":"#waline","comment":true,"libUrl":"//unpkg.com/@waline/client@v2/dist/waline.js","path":"/"}</script>
<link rel="stylesheet" href="https://unpkg.com/@waline/client@v2/dist/waline.css">
<script>
document.addEventListener('page:loaded', () => {
  NexT.utils.loadComments(CONFIG.waline.el).then(() =>
    NexT.utils.getScript(CONFIG.waline.libUrl, { condition: window.Waline })
  ).then(() => 
    Waline.init(Object.assign({}, CONFIG.waline,{ el: document.querySelector(CONFIG.waline.el) }))
  );
});
</script>

</body>
</html>

<!-- 页面点击小红心 -->
<script type="text/javascript" src="/js/src/clicklove.js"></script>
